On Proximity and other Distance Parameters in Planar Graphs

Peter Dankelmann, Sonwabile Mafunda, Sufiyan Mallu · 2025

Read On Proximity and other Distance Parameters in Planar Graphs by Peter Dankelmann, Sonwabile Mafunda, Sufiyan Mallu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-10078.txt.

Introduction

Peter Dankelmann, Sonwabile Mafunda, and Sufiyan Mallu study how spread out the points of a flat network can be. Their 2025 paper uses the mean distance from each point to all others. The smallest such mean is called proximity, and the largest is called remoteness. Past work set broad caps on gaps between these values for any linked network.

The authors show much tighter caps for flat networks that use all possible links, and for networks with strong links between parts. Like results hold for four-sided flat networks and for flat networks drawn in a ring. They give sample networks that show their caps are sharp or near sharp.

Catalog record

CREATORPeter Dankelmann, Sonwabile Mafunda, Sufiyan Mallu
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE47 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-10078

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On Proximity and other Distance Parameters in Planar Graphs Peter Dankelmann, Sonwabile Mafunda, Sufiyan Mallu Abstract Let G G be a connected graph. The average distance of a vertex v v of G G is the arithmetic mean of the distances from v v to all other vertices of G G . The proximity and remoteness of G G are defined as the minimum and maximum, respectively, of the average distances of the vertices of G 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 n , the difference between remoteness and proximity and the difference between radius and proximity are bounded from above by about n 4 \frac{n}{4} , and the difference between diameter and proximity is bounded from above by about 3 4 ​ n \frac{3}{4}n . In this paper, we show that all three bounds can be improved significantly for maximal planar graphs, and for graphs of given connectivity. We show that in maximal planar graphs the above bound on the difference between radius and proximity can be improved to about 1 12 ​ n \frac{1}{12}n , and further to about 1 16 ​ n \frac{1}{16}n and 1 20 ​ n \frac{1}{20}n if the graphs is, in addition, 4 4 -connected or 5 5 -connected, respectively. Similar improvements are shown for quadrangulations, and for maximal outerplanar graphs. We further show that the above bound on the difference between remoteness and proximity can be improved to about 1 4 ​ κ ​ n \frac{1}{4\kappa}n if G G is κ \kappa -connected. Finally, we improve the bound on the difference between diameter and proximity to about 3 4 ​ κ ​ n \frac{3}{4\kappa}n if G 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: Remoteness; proximity; minimum status; planar graph; outerplanar graph; radius MSC-class: 05C12 1 Introduction In this paper we consider finite, connected graphs with no loops or multiple edges. In a connected graph G of order n\geq 2 with vertex set V , the average distance \bar{\sigma}_{G}(v) of a vertex is defined to be the arithmetic mean of the distances from v to all other vertices of G , i.e., \overline{\sigma}_{G}(v)=\frac{1}{n-1}\sum_{w\in V}d_{G}(v,w) , where the distance d_{G}(v,w) denotes the usual shortest path distance. The proximity \pi(G) and remoteness \rho(G) of G are defined as the minimum and maximum, respectively, of the average distances of the vertices of G , i.e., \pi(G)={\rm min}_{v\in V}\bar{\sigma}_{G}(v),\quad\rho(G)={\rm max}_{v\in V}\bar{\sigma}_{G}(v). The terms proximity and remoteness were first used in a paper on automated comparison of graph invariants [ 3 ] , and are in wide use nowadays. However, the proximity of graphs and closely related concepts had been studied before under different names. Zelinka [29] studied the vertex deviation , defined as \frac{\sigma_{G}(v)}{n} , where \sigma_{G}(v) denotes the sum of the distances between v and all other vertices, and n is the number of vertices. Also the name minimum status , defined as \min_{v\in V(G)}\sigma(v) has been used (see, for example, [ 19 ] ). Bounds on proximity and remoteness in terms of order only were given by Zelinka [ 30 ] and later, independently, by Auochiche and Hansen [ 5 ] . Theorem 1.1 . (Zelinka [ 30 ] , Aouchiche, Hansen [ 5 ] ) (a) Let G be a connected graph of order n\geq 2 . Then \pi(G)\leq\left\{\begin{array}[]{cc}\frac{n+1}{4}&\textrm{if $n$ is odd,}\\ \frac{n+1}{4}+\frac{1}{4(n-1)}&\textrm{if $n$ is even,}\end{array}\right. with equality if and only if G is either a path or a cycle. (b) Let G be a connected graph of order n\geq 2 . Then \rho(G)\leq\frac{n}{2}, with equality if and only if G is a path. Relations between proximity and other graph parameters have been studied, for example girth [ 6 ] , maximum degree see [ 15 , 20 , 23 ] clique number see [ 17 ] , matching number and domination number [ 19 , 24 ] , radius [ 26 ] distance eigenvalues [ 21 ] . The proximity of trees with no vertex of degree 2 was investigated in [ 8 ] . For a recent survey on proximity and remoteness in graphs see [ 7 ] . Recently, directed versions of proximity and remoteness were introduced by Ai, Gerke, Gutin and Mafunda [ 1 ] , who proved the following bound. Theorem 1.2 . (Ai, Gerke, Gutin, Mafunda [ 1 ] ) Let D be a strong digraph of order n\geq 3 . Then 1\leq\pi(D)\leq\frac{n}{2}, 1\leq\rho(D)\leq\frac{n}{2}, and both bounds are sharp. It was shown in [ 11 ] that the bounds in Theorem 1.1 can be improved by a factor of about \frac{3}{\delta+1} for graphs of minimum degree \delta . In [ 13 ] , these bounds were improved further for graphs not containing cycles of length 3 or 4 . For maximal planar graphs and related types of graphs, the following bounds on proximity and remoteness were given in [ 10 ] and [ 9 ] , respectively. Theorem 1.3 . (Czabarka, Dankelmann, Olsen, Székely [ 9 ] ) (a) If G is a maximal planar graph of order n , then \rho(G)\leq\frac{n+2}{6}+\varepsilon_{n},\quad\pi(G)\leq\frac{n+19}{12}+\frac{25}{3(n-1)}, where \varepsilon_{n}=0 if n\equiv 1\pmod{3} , and \varepsilon_{n}=\frac{1}{3(n-1)} otherwise. (b) If G is a 4 -connected maximal planar graph of order n , then \rho(G)\leq\frac{n+3}{8}+\varepsilon_{n},\quad\pi(G)\leq\frac{n+35}{16}+\frac{91}{4(n-1)}, where \varepsilon_{n}=0 if n\equiv 1\pmod{4} , \varepsilon_{n}=\frac{1}{2(n-1)} if n\equiv 3\pmod{4} , and \varepsilon_{n}=\frac{3}{8(n-1)} otherwise. (c) If G is a 5 -connected maximal planar graph of order n , then \rho(G)\leq\frac{n+4}{10}+\varepsilon_{n},\quad\pi(G)\leq\frac{n+57}{20}+\frac{393}{10(n-1)}, where \varepsilon_{n}=-\frac{3}{5(n-1)} if n\equiv 0\pmod{5} , \varepsilon_{n}=-\frac{1}{n-1} if n\equiv 1\pmod{5} , \varepsilon_{n}=\frac{2}{5(n-1)} if n\equiv 2\pmod{5} , and \varepsilon_{n}=-\frac{2}{5(n-1)} otherwise. In (a)-(c), the bounds on remoteness are sharp, and the bounds on proximity are sharp apart from an additive constant. Bounds on proximity and remoteness in outerplanar graphs in terms of order and maximum face length were given in [ 16 ] . It is natural to ask how large the differences between proximity, remoteness, and other distance parameters can be. This question was answered for the difference between proximity and remoteness by Aouchiche and Hansen [ 5 ] , who obtained the following sharp bound. Theorem 1.4 . (Aouchiche, Hansen [ 5 ] ) Let G be a connected graph of order n\geq 3 . Then \rho(G)-\pi(G)\leq\left\{\begin{array}[]{ll}\dfrac{n-1}{4}\;\quad\qquad\;\;\quad\;\;\;\;\;\mbox{if n is odd,}\\ \\ \dfrac{n-1}{4}-\dfrac{1}{4(n-1)}\;\quad\mbox{if n is even.}\\ \end{array}\right. Equality holds if and only if G is a graph constructed by joining an endpoint of a path P_{\lceil\frac{n}{2}\rceil} with any vertex of a connected graph H on \lfloor\frac{n}{2}\rfloor+1 vertices. Aouchiche and Hansen [ 5 ] determined also the maximum differences between diameter and proximity, and between radius and proximity in a connected graph. Theorem 1.5 . (Aouchiche, Hansen [ 5 ] ) Let G be a connected graph of order n\geq 3 . Then {\rm diam}(G)-\pi(G)\leq\left\{\begin{array}[]{cc}\frac{3n-5}{4}&\textrm{if $n$ is odd,}\\ \frac{3n-5}{4}-\frac{1}{4n-4}&\textrm{if $n$ is even.}\end{array}\right. Equality holds if and only if G is a path. Theorem 1.6 . (Aouchiche, Hansen [ 5 ] ) Let G be a connected graph of order n\geq 3 . Then {\rm rad}(G)-\pi(G)\leq\left\{\begin{array}[]{cc}\frac{n-1}{4}-\frac{1}{n-1}&\textrm{if $n$ is odd,}\\ \frac{n-1}{4}-\frac{1}{4n-4}&\textrm{if $n$ is even.}\end{array}\right. and this bound is sharp.

Read the complete text