Proximity in triangulations and quadrangulations
Abstract
Let G be a connected graph. If σ(v) denotes the arithmetic mean of the distances from v to all other vertices of G, then the proximity, π(G), of G is defined as the smallest value of σ(v) over all vertices v of G. We give upper bounds for the proximity of simple triangulations and quadrangulations of given order and connectivity. We also construct simple triangulations and quadrangulations of given order and connectivity that match the upper bounds asymptotically and are likely optimal.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.5614/ejgta.2022.10.2.7
References
P. Ali, P. Dankelmann, and S. Mukwembi, The radius of k-connected planar graphs with bounded faces, Discrete Appl. Math. 312 (2012), 3636–3642.
P. Ali, P. Dankelmann, M.J. Morgan, S. Mukwembi, H.C. Swart, and T. Vetrík (2018), The average eccentricity, spanning trees of plane graphs, size and order. Utilitas Math 107 (2018), 37–49.
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.
M. Aouchiche, and P. Hansen, Nordhaus-Gaddum relations for proximity and remoteness in graphs, Comput. Math. Appl. 59(8) (2010), 2827–2835.
M. Aouchiche and P. Hansen, Proximity and remoteness in graphs: results and conjectures, Networks 58(2) (2011), 95–102.
C.A. Barefoot, R.C. Entringer, and L.A. Székely, Extremal values for ratios of distances in trees, Discrete Appl. Math. 80 (1997), 37–56.
R. Bowen and S. Fisk, Generation of Triangulations of the Sphere, Math. Comp. 21 (1967), 250–252.
G. Brinkmann, S. Greenberg, C. Greenhill, B.D. McKay, R. Thomas, and P. Wollan, Generation of simple quadrangulations of the sphere. Discrete Math. 305(1) (2005), 33–54.
G. Brinkmann and B. McKay Construction of planar triangulations with minimum degree 5. Disc. Math. 301 (2005), 147–163.
Z. Che, K.L. Collins, An upper bound on Wiener indices of maximal planar graphs. Discrete Appl. Math. 258 (2019), 76–86.
É. Czabarka, P. Dankelmann, T. Olsen and L. A. Székely, Wiener Index and Remoteness in Triangulations and Quadrangulations. Discrete Mathematics & Theoretical Computer Science 23(1) (2021).
P. Dankelmann, Proximity, remoteness, and minimum degree. Discrete Appl. Math. 184 (2015), 223–228.
P. Dankelmann, New bounds on proximity and remoteness in graphs. Communications in Combinatorics and Optimization 1(1) (2016), 28–40. J..K. Doyle, J.E. Graver, Mean distance in a graph. Discrete Math. 7 (1977), 147–154.
R.C. Entringer, D.E. Jackson, and D.A. Snyder, Distance in graphs. Czech Math. J. 26 (1976), 283–296.
D. Ghosh, E. Gyri, A. Paulos, N. Salia, and O. Zamora, The maximum Wiener index of maximal planar graphs. Journal of Combinatorial Optimization 40 (2020), 1121–-1135.
E. Gyri, A. Paulos, and C. Xiao, Wiener index of quadrangulation graphs. Discrete Applied Mathematics 289 (2021), 262–269.
F. Lutz. Enumeration and random realization of triangulated surfaces. Discrete Diff. Geo. OWS 38 (2008), 235–253.
B. Ma, B. Wu, and W. Zhang, Proximity and average eccentricity of a graph. Inform. Process. Lett. 112(10) (2012), 392–395.
G. I. Miller. Finding small cycle separators for 2-connected planar graphs. J. Comput. Sys. Sci. 32(3) (1986), 265–279.
M. Scheucher, H. Schrezenmaier, and R. Steiner, A note on universal point sets for planar graphs. Journal of Graph Algorithms and Applications 24(3) (2020), 247–267.
B. Wu and W. Zhang, Average distance, radius and remoteness of a graph. Ars Math. Contemp. 7 (2014), 441–452.
B. Zelinka, Medians and peripherians of trees. Arch. Math. (Brno) 4 (1968), 87–95.
Refbacks
- There are currently no refbacks.
ISSN: 2338-2287
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.