Proximity and Radius in Outerplanar Graphs with Bounded Faces
Peter Dankelmann, Sonwabile Mafunda, Sufiyan Mallu · 2025
Read Proximity and Radius in Outerplanar Graphs with Bounded Faces 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-10077.txt.
Introduction
Peter Dankelmann, Sonwabile Mafunda, and Sufiyan Mallu study distances inside a special family of graphs, in a two thousand twenty-five mathematics paper. Outerplanar graphs can be drawn with all vertices on a circle and no crossing edges. Two measures matter here: proximity, based on average distances, and radius, based on worst-case distances.
The authors bound the proximity of two-connected outerplanar graphs. Their bound uses the graph's order and its maximum face length. It is sharp apart from a small additive constant. For radius, a known bound for maximal outerplanar graphs is extended. It now covers all two-connected outerplanar graphs whose faces are not too long. The results refine how graph shape controls distance.
Catalog record
| CREATOR | Peter Dankelmann, Sonwabile Mafunda, Sufiyan Mallu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 36 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-10077
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Proximity and Radius in Outerplanar Graphs with Bounded Faces Peter Dankelmann, Sonwabile Mafunda, Sufiyan Mallu Abstract Let G G be a finite, connected graph and v v a vertex of G G . The average distance and the eccentricity of v v in G G are defined as the arithmetic mean and the maximum, respectively, of the distances from v v to all other vertices of G G . The proximity of G G and the radius of G G are defined as the minimum of the average distances and the eccentricities over all vertices of G G . In this paper, we establish an upper bound on the proximity of a 2 2 -connected outerplanar graphs in terms of order and maximum face length. This bound is sharp apart from a small additive constant. It is known that the radius of a maximal outerplanar graph is at most ⌊ n 4 ⌋ + 1 \lfloor\frac{n}{4}\rfloor+1 . In the second part of this paper we show that this bound on the radius holds for a much larger subclass of outerplanar graphs, for all 2 2 -connected outerplanar graphs of order n n whose maximum face length does not exceed n + 2 4 \frac{n+2}{4} . Keywords: Radius; remoteness; proximity; minimum status; planar graph; outerplanar graph MSC-class: 05C12 1 Introduction Let G be a finite, connected graph of order n\geq 2 with vertex set V(G) . The average distance \overline{\sigma}(v,G) and the eccentricity {\rm ecc}(v,G) of a vertex v\in V(G) are defined as the arithmetic mean and the maximum, respectively, of the distances from v to all other vertices of G , i.e. \overline{\sigma}(v,G)=\frac{1}{n-1}\sum_{u\in V(G)}d(v,u) , {\rm ecc}(v,G)=\max_{u\in V(G)}d(v,u) , where d(v,u) denotes the usual shortest path distance between vertices v and u . The proximity \pi(G) of G is defined as \min_{v\in V(G)}\overline{\sigma}(v,G) . The radius {\rm rad}(G) of G is \min_{v\in V(G)}{\rm ecc}(v,G) . We note that the proximity is closely related to the minimum status of a graph, which is defined as (n-1)\pi(G) . A bound on proximity and remoteness (defined as the maximum of the average distances of the vertices, denoted by \rho(G) ), in terms of order was determined by Zelinka [ 36 ] and later, independently, by Aouchiche and Hansen [ 3 ] , who introduced the names proximity and remoteness. Theorem 1.1 . (Zelinka [ 36 ] , Aouchiche, Hansen [ 3 ] ) Let G be a connected graph of order n\geq 2 . Then 1\leq\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. The lower bound holds with equality if and only if G has a vertex of degree n-1 . The upper bound holds with equality if and only if G is a path or a cycle. Also, 1\leq\rho(G)\leq\frac{n}{2}. The lower bound holds with equality if and only if G is a complete graph. The upper bound holds with equality if and only if G is a path. The following bound on radius is folklore. Proposition 1.2 . Let G be a connected graph of order n . Then {\rm rad}(G)\leq\frac{n}{2}. Since by Theorem 1.1 the graphs that maximise the proximity among graphs of given order have only vertices of small degree, it is natural to expect improved bounds if also vertex degrees are taken into account. It was shown by Dankelmann [ 13 ] that for graphs of minimum degree \delta\geq 3 , the bound in Theorem 1.1 can be improved by a factor of about \frac{3}{\delta+1} . For further results on proximity involving minimum degree see [ 14 , 15 , 16 ] . Rissner and Burkhard [ 33 ] determined trees that minimise and maximise the proximity among all trees of given order and maximum degree. For a bound that takes into account both, maximum and minimum degree, see [ 17 ] . Bounds on the proximity of trees in terms of order and among others, number of vertices of odd degree were given by Peng and Zhou [ 32 ] . Guo and Zhou [ 21 ] determined the trees that minimise the proximity among all trees with a given degree sequence. Several relations between proximity and other distance based graph parameters were proved by Aouchiche and Hansen [ 3 ] . Hua and Das [ 22 ] resolved conjectures relating proximity or remoteness to average distance of the graph (defined as the arithmetic mean of the distances between all pairs of vertices), maximum degree and average degree. They also found relations between proximity, remoteness and clique number (defined as the order of a largest complete subgraph). The maximum value of the difference between average eccentricity (defined as the arithmetic mean of the eccentricities of the vertices of G ) and proximity was determined by Ma, Wu and Zhang [ 27 ] . Pei et al. [ 31 ] determined the maximum difference between domination number (defined as the minimum cardinality of a set of vertices of G so that every vertex not in the set is adjacent to some vertex in the set) and proximity. The differences between average distance and proximity and between average eccentricity and remoteness were considered by Sedlar [ 34 ] . For relations between proximity, remoteness and girth (defined as the length of a shortest cycle) see [ 4 ] . Also proximity in various graph classes has been explored. Barefoot, Entringer and Szekély [ 6 ] obtained results on proximity and remoteness in trees. Several results for trees with no vertex of degree 2 were obtained by Chen, Lin and Zhou [ 9 ] . Best possible bounds on proximity and remoteness in maximal planar graphs and related graphs were proved by Czabarka et al. in [ 10 , 11 ] , see also [ 18 ] . Recently, the bound in Theorem 1.1 was extended to digraphs by Ai, Gerke, Gutin and Mafunda [ 1 ] . Further results can be found in the survey on proximity and remoteness in graphs in [ 5 ] . The radius of graphs has been studied extensively in the literature. The bound in Proposition 1.2 has been improved by a factor of about \frac{3}{\delta+1} for graphs of minimum degree \delta in [ 19 ] (see also [ 25 , 30 ] ). We only mention here the following bounds on the radius pertinent to the present paper. It is well-known that the diameter of a connected graph cannot exceed twice the radius. It was shown in [ 7 ] that for chordal graphs, i.e., graphs with no induced cycle of length greater than 3 , the diameter is always close to twice the radius. Bounds on the radius of maximal planar graphs and planar graphs with bounded face length were given in [ 2 ] . The starting point for this paper is the observation that the bounds on proximity in Theorem 1.1 and radius in Proposition 1.2 can be improved significantly (to about \frac{n}{12} for proximity [ 11 ] and to about \frac{n}{6} for the radius [ 2 ] ) for maximal planar graphs. The latter bound was generalised to planar graphs with given maximum face length. The goal of this paper is to prove corresponding bounds on proxmitiy and radius for