New bounds on proximity and remoteness in graphs

Document Type : Original paper

Author

University of Johannesburg

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 defined as the minimum and maximum, respectively, average distance of the vertices of $G$. In this paper we investigate the difference between proximity or remoteness and the classical distance parameters diameter and radius. Among other results we show that in a graph of order $n$ and minimum degree $\delta$ the difference between diameter and proximity and the difference between radius and proximity cannot exceed $\frac{9n}{4(\delta+1)}+c_1$ and $\frac{3n}{4(\delta+1)}+c_2$, respectively, for constants $c_1$ and $c_2$ which depend on $\delta$ but not on $n$.  These bounds improve bounds by Aouchiche and Hansen \cite{AouHan2011} in terms of order alone by about a factor of $\frac{3}{\delta+1}$. We further give lower bounds on the remoteness in terms of diameter or radius. Finally we show that the average distance of a graph, i.e., the average of the distances between all pairs of vertices, cannot exceed twice the proximity.

Keywords

Main Subjects

References

[1] M. Aouchiche, G. Caporossi, and P. Hansen. Variable Neighbourhood Search for Extremal Graphs, 20 Automated Comparison of Graph Invariants. MATCH Commun. Math. Comput. Chem. 58 (2007), 365-384.
[2] M. Aouchiche and P. Hansen. Nordhaus-Gaddum relations for proximity and remoteness in graphs. Comput. Math. Appl. 59(no. 8) (2010), 2827-2835.
[3] M. Aouchiche, P. Hansen. Proximity and remoteness in graphs: results and conjectures. Networks 58 (no. 2) (2011), 95-102.
[4] C.A. Barefoot, R.C. Entringer, and L.A. Sz´ekely. Extremal values for ratios of distances in trees. Discrete Appl. Math. 80 (1997), 37-56.
[5] P. Dankelmann,G. Dlamini, and H.C. Swart. Uppper bounds on distance measures in K2,l-free graphs. (manuscript)
[6] P. Dankelmann. Proximity, remoteness, and minimum degree. Discrete Appl. Math. 184 (2015), 223-228.
[7] G. Dlamini. Aspects of distances in graphs, Ph.D. Thesis, University of Natal, Durban, 2003. [8] R.C. Entringer, D.E. Jackson, and D.A. Snyder. Distance in graphs. Czechoslovak Math. J. 26 (101) no. 2 (1976), 283-296.
[9] P. Erd¨os, J. Pach,R. Pollack, and Z. Tuza. Radius, diameter, and minimum degree. J. Combin. Theory Ser. B 47 (1989) 73-79.
[10] B. Ma, B. Wu, and W. Zhang. Proximity and average eccentricity of a graph. Inform. Process. Lett. 112(no. 10) (2012), 392-395.
[11] B. Wu and W. Zhang. Average distance, radius and remoteness of a graph. Ars Math. Contemp. 7 (2014), 441-452.
[12] B. Zelinka. Medians and peripherians of trees. Arch. Math. (Brno) 4 (1968), 87-95.
 

Files

Share

How to cite

Statistics