On proximity and other distance parameters in planar graphs

Articles in Press

Document Type : Special issue of CCO to honor Odile Favaron

Authors

1 University of Johannesburg, South Africa

2 Soka University in America, USA

Abstract

Let $G$ be a connected graph. The average distance of a vertex $v$ of $G$ is the arithmetic mean of the distances from $v$ to all other vertices of $G$. The proximity and remoteness of $G$ are defined as the minimum and maximum, respectively, of the average distances of the vertices of $G$.
It was shown by Aouchiche and Hansen [Proximity and remoteness in graphs: bounds and conjectures, Networks 58 no. 2 (2011)] that for a connected graph of order $n$, the difference between remoteness and proximity and the difference between radius and proximity are bounded from above by about $\frac{n}{4}$, and the difference between diameter and proximity is bounded from above by about $\frac{3}{4}n$.
In this paper, we show that all three bounds can be improved significantly for simple triangulations (i.e., triangulations), and for graphs of given connectivity.
We show that in simple triangulations the above bound on the difference between radius and proximity can be improved to about $\frac{1}{12}n$, and further to about $\frac{1}{16}n$ and $\frac{1}{20}n$ if the graphs is, in addition, $4$-connected or $5$-connected, respectively. Similar improvements are shown for simple quadrangulations (i.e., maximal bipartite planar graphs), and for maximal outerplanar graphs. We further show that the above bound on the difference between remoteness and proximity can be improved to about $\frac{1}{4\kappa}n$ if $G$ is $\kappa$-connected.
Finally, we improve the bound on the difference between diameter and proximity to about $\frac{3}{4\kappa}n$ if $G$ is $\kappa$-connected. We present graphs that demonstrate that our bounds are either sharp, or sharp apart from an additive constant, even if restricted to planar graphs.

Keywords

Main Subjects

References

[1] J. Ai, S. Gerke, G. Gutin, and S. Mafunda, Proximity and remoteness in directed and undirected graphs, Discrete Math. 344 (2021), no. 3, 112252. https://doi.org/10.1016/j.disc.2020.112252
[2] P. Ali, P. Dankelmann, and S. Mukwembi, The radius of $k$-connected planar graphs with bounded faces, Discrete Appl. Math. 312 (2012), no. 24, 3636–3642. https://doi.org/10.1016/j.disc.2012.08.019
[3] 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), no. 2, 365–384.
[4] M. Aouchiche and P. Hansen, Proximity and remoteness in graphs: Results and conjectures, Networks 58 (2011), no. 2, 95–102. https://doi.org/10.1002/net.20450
[5] M. Aouchiche and P. Hansen, Proximity, remoteness and girth in graphs, Discrete Appl. Math. 222 (2017), 31–39. https://doi.org/10.1016/j.dam.2017.01.025
[6] M. Aouchiche and B.A. Rather, Proximity and remoteness in graphs: A survey, Discrete Appl. Math. 353 (2024), 94–120.
https://doi.org/10.1016/j.dam.2024.04.012
[7] Z. Che and K.L. Collins, An upper bound on Wiener indices of maximal planar graphs, Discrete Appl. Math. 258 (2019), 76–86. https://doi.org/10.1016/j.dam.2018.11.026
[8] M. Cheng, H. Lin, and B. Zhou, Minimum status of series-reduced trees with given parameters, Bull. Braz. Math. Soc., New Series 53 (2022), 701–720. https://doi.org/10.1007/s00574-021-00278-1
[9] E. Czabarka, P. Dankelmann, T. Olsen, and L.A. Székely, Wiener index and remoteness in triangulations and quadrangulations, Discrete Math. Theor. Comp. Sci. 23 (2021), no. 1, #3. https://doi.org/10.46298/dmtcs.6473
[10] E. Czabarka, P. Dankelmann, T. Olsen, and L.A. Székely, Proximity in triangulations and quadrangulations, Electron. J. Graph Theory Appl. 10 (2022), no. 2, 425–446. https://doi.org/10.5614/ejgta.2022.10.2.7
[11] P. Dankelmann, Proximity, remoteness, and minimum degree, Discrete Appl. Math. 184 (2015), 223–228. https://doi.org/10.1016/j.dam.2014.11.012
[12] P. Dankelmann, New bounds on proximity and remoteness in graphs, Commun. Comb. Optim. 1 (2016), no. 1, 29–41. https://doi.org/10.22049/cco.2016.13543
[13] P. Dankelmann, E. Jonck, and S. Mafunda, Proximity and remoteness in trianglefree and C4-free graphs in terms of order and minimum degree, Discrete Math. 344 (2021), no. 9, 112513. https://doi.org/10.1016/j.disc.2021.112513
[14] P. Dankelmann and S. Mafunda, On the difference between proximity and other distance parameters in triangle-free graphs and C4-free graphs, Discrete Appl. Math. 321 (2022), 295–307. https://doi.org/10.1016/j.dam.2022.06.037
[15] P. Dankelmann, S. Mafunda, and S. Mallu, Proximity, remoteness and maximum degree in graphs, Discrete Math. Theoretical Comp. Science 24 (2022), no. 2, #10. https://doi.org/10.46298/dmtcs.9432
[16] P. Dankelmann, S. Mafunda, and S. Mallu, Proximity and radius in outerplanar graphs with bounded faces, Discrete Math. 349 (2026), no. 11, 115250. https://doi.org/10.1016/j.disc.2026.115250
[17] A.J. Goldman, Minimax location of a facility in a network, Trans. Sci. 6 (1972), no. 4, 407–418. https://doi.org/10.1287/trsc.6.4.407
[18] S.L. Hakimi, Optimum locations of switching centers and the absolute centers and medians of a graph, Oper. Res. 12 (1964), no. 3, 450–459.
[19] H. Hua, Y. Chen, and K.C. Das, The difference between remoteness and radius of a graph, Discrete Appl. Math. 187 (2015), 103–110. https://doi.org/10.1016/j.dam.2015.02.007
[20] H. Hua and K.C. Das, Proof of conjectures on remoteness and proximity in graphs, Discrete Appl. Math. 171 (2014), 72–80. https://doi.org/10.1016/j.dam.2014.02.011
[21] J. Leydold and P.F. Stadler, Minimal cycle bases of outerplanar graphs, The Electronic Journal of Combinatorics 5 (1998), no. 1, #R16. https://doi.org/10.37236/1354
[22] C. Liang, B. Zhou, and H. Guo, Minimum status, matching and domination of graphs, The Computer Journal 64 (2021), no. 9, 1384–1392.
[23] C. Lin, W.H. Tsai, J.L. Shang, and Y.J. Zhang, Minimum statuses of connected graphs with fixed order and maximum degree, J. Comb. Optim. 24 (2012), 147–161. https://doi.org/10.1007/s10878-011-9412-4
[24] H. Lin, K.C. Das, and B. Wu, Remoteness and distance eigenvalues of a graph, Discrete Appl. Math. 215 (2016), 218–224. https://doi.org/10.1016/j.dam.2016.07.018
[25] B. Ma, B. Wu, and W. Zhang, Proximity and average eccentricity of a graph, Inform. Process. Lett. 112 (2012), no. 10, 392–395. https://doi.org/10.1016/j.ipl.2012.02.001
[26] S. Mallu, Bounds on proximity and remoteness in graphs and digraphs, Ph.D. thesis, University of Johannesburg, Johannesburg, Gauteng, South Africa, 2026.
[27] L. Pei, X. Pan, K. Wang, and J. Tian, Proofs of the AutoGraphiX conjectures on the domination number, average eccentricity and proximity, Discrete Appl. Math. 289 (2021), 292–301. https://doi.org/10.1016/j.dam.2020.11.012
[28] Z. Peng and B. Zhou, Minimum status of trees with given parameters, RAIROOper. Res. 55 (2021), S765–S785.
https://doi.org/10.1051/ro/2020015
[29] R. Rissner and R.E. Burkard, Bounds on the radius and status of graphs, Networks 64 (2014), no. 2, 76–83.
https://doi.org/10.1002/net.21558
[30] J. Sedlar, Remoteness, proximity and few other distance invariants in graphs, Filomat 27 (2013), no. 8, 1425–1435.
https://doi.org/10.2298/FIL1308425S
[31] M.E. Watkins, A lower bound for the number of vertices of a graph, The American Mathematical Monthly 74 (1967), no. 3, 297–297.
[32] H. Whitney, 2-Isomorphic graphs, Amer. J. Math. 55 (1933), no. 1, 245–254.
[33] B. Wu and W. Zhang, Average distance, radius and remoteness of a graph, Ars Math. Contemp. 7 (2014), no. 2, 441–452.
[34] B. Zelinka, Medians and peripherians of trees, Arch. Math. (Brno) 4 (1968), no. 2, 87–95.
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 18 June 2026

Files

Share

How to cite

Statistics