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 π(G) and the remoteness ρ(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 δ the difference between diameter and proximity and the difference between radius and proximity cannot exceed 9n4(δ+1)+c1 and 3n4(δ+1)+c2, respectively, for constants c1 and c2 which depend on δ but not on n.  These bounds improve bounds by Aouchiche and Hansen \cite{AouHan2011} in terms of order alone by about a factor of 3δ+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