Proximity, remoteness and maximum degree in graphs

Abstract

The average distance of a vertex $v$ of a connected graph $G$ is the arithmetic mean of the distances from $v$ to all other vertices of $G$. The proximity $\pi (G)$ and the remoteness $\rho (G)$ of $G$ are the minimum and the maximum of the average distances of the vertices of $G$, respectively. In this paper, we give upper bounds on the remoteness and proximity for graphs of given order, minimum degree and maximum degree. Our bounds are sharp apart from an additive constant.

20 pages

References in corpus (3)

• Wiener index in graphs with given minimum degree and maximum degree
• Proximity in Triangulations and Quadrangulations
• On the difference between proximity and other distance parameters in triangle-free graphs and $C_4$-free graphs