Proximity in triangulations and quadrangulations

Éva Czabarka (Department of Mathematics, University of South Carolina, Columbia, SC 29208 USA, and Visiting Professor, Department of Pure and Applied Mathematics, University of Johannesburg, P.O. Box 524, Auckland Park, Johannesburg 2006, South Africa)
Peter Dankelmann (Department of Pure and Applied Mathematics, University of Johannesburg, P.O. Box 524, Auckland Park, Johannesburg 2006, South Africa)
Trevor Olsen (Department of Mathematics, University of South Carolina, Columbia, SC 29208 USA)
László Székely (Department of Mathematics, University of South Carolina, Columbia, SC 29208 USA, and Visiting Professor, Department of Pure and Applied Mathematics, University of Johannesburg, P.O. Box 524, Auckland Park, Johannesburg 2006, South Africa)

Electronic Journal of Graph Theory and Applications (EJGTA)
Vol 10, No 2 (2022): Electronic Journal of Graph Theory and Applications

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.