Eva Czabarka ´ ^∗a , Peter Dankelmann^b , Trevor Olsen^c , Laszl ´ o A. Sz ´ ekely ´ a

aDepartment 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

^bDepartment of Pure and Applied Mathematics, University of Johannesburg, P.O. Box 524, Auckland Park, Johannesburg 2006, South Africa

^cDepartment of Mathematics, University of South Carolina, Columbia, SC 29208 USA

czabarka@math.sc.edu, pdankelmann@uj.ac.za, tvolsen@math.sc.edu, szekely@math.sc.edu

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: distance, maximal, average distance, planar graph, triangulation, quadrangulation, connectivity, proximity, upper bounds

Mathematics Subject Classification: 05C12

DOI: 10.5614/ejgta.2022.10.2.7

1. Introduction

Let G be a connected graph with vertex set V (G), and let v be a vertex of G. The total distance σ(v) and the average distance σ(v) of v is defined as the sum and the average, respectively, of the distances from v to all other vertices. Bounds on σ(v) were obtained, for example, in [6] [15] and

^∗ corresponding author

²³ January 2020, Revised: 16 April 2022, Accepted: 6 May 2022.

[23]. Of particular interest are the minimum value and the maximum value over all \(v \in V(G)\) of \(\overline{\sigma}(v)\) in a graph G, usually referred to as the proximity \(\pi(G)\) and the remoteness \(\rho(G)\), respectively, of G. A closely related graph invariant is the minimum status of G, defined as the minimum value over all \(v \in V(G)\) of \(\sigma(v)\).

It was shown by Zelinka [23] and, independently, by Aouchiche and Hansen [5] that the proximity and remoteness of a connected graph of order n are at most approximately \(\frac{n}{4}\) and \(\frac{n}{2}\), respectively. For graphs of given minimum degree \(\delta\) these bounds were improved in [12] by a factor of about \(\frac{3}{\delta+1}\). The difference between remoteness and proximity in a connected graph of order n was shown to be at most about \(\frac{n}{4}\) (see [5]), and this was improved by a factor of about \(\frac{3}{\delta+1}\) in [13]. For more recent results on proximity and remoteness see, for example, [19] and [22].

This paper is concerned with bounds on the proximity of triangulations, i.e., maximal planar graphs, and quadrangulations, i.e., maximal bipartite planar graphs. Several bounds on distance measures in maximal planar graphs are known, for example for radius [1], average eccentricity [2], Wiener index [10, 11, 16, 17]. (The Wiener index of a graph is the sum of the distances between all unordered pairs of graphs. The radius is the smallest of the eccentricities of the vertices of a graph, where the eccentricity of a vertex v is the distance to a vertex farthest from v.) Sharp upper bounds on the remoteness of maximum planar graphs were given in [10] and [11], in the latter one sharp upper bounds on the remoteness of maximum bipartite planar graphs as well. However, no bound on the proximity of maximum planar graphs appears to be known. The aim of this paper is to fill this gap and give upper bounds on proximity of simple triangulations and quadrangulations of given order and connectivity. Our matching constructions make these bounds tight within an additive constant. We conjecture that these constructions are of maximum proximity in their respective classes. It is a tedious routine calculation to determine the minimum status (i.e. the conjectured maximum proximity in the respective class) in the constructions, we just provide the results in formulae (1), (2), (3), (4), and (5). Remarkably, all of the structures we found to maximize the proximity are identical to the structures we conjecture to maximize the Wiener Index in [11]. Similarly, the structures match the graphs which maximize the remoteness, outside of 5-connected triangulations on 5k + 3 vertices.

The notation we use in this paper is as follows. If G is a graph, then we denote its vertex set by V(G), and by n(G) we mean the order, defined as |V(G)|. The eccentricity e(v) of a vertex v is the distance to a vertex farthest from v, i.e., \(e(v) = \max_{u \in V(G)} d_G(v, u)\). The largest and the smallest of the eccentricities of the vertices of G are the diameter and the radius of G, respectively. The neighbourhood of a vertex v of G is the set of vertices adjacent to v, it is denoted by \(N_G(v)\), and the cardinality \(|N_G(v)|\) is the degree of v, which we denote by \(\deg_G(v)\). If i is an integer with \(0 \le i \le e(v)\), then \(N_i(v)\) denotes the set of all vertices at distance exactly i from v, and we write \(n_i(v)\) for \(|N_i(v)|\). If there is no danger of confusion, we often omit the subscript G or the argument G or v. If i is an integer with i and i if i is an integer with i and i if i is an integer of edges that join a vertex in i to a vertex in i if i is an integer with i if i is an integer with i if i is an integer with i if i is an integer with i if i is an integer with i if i is an integer with i if i if i is an integer with i if i is an integer with i if i is an integer with i if i is an integer with i if i if i is an integer with i if i is an integer with i if i if i is an integer with i if i if i is an integer with i if i is an integer with i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if i if

We say that a graph G is k-connected, \(k \in \mathbb{N}\), if deleting fewer than k vertices from G always leaves a connected graph.

2. Upper bounds on proximity of triangulations and quadrangulations

In this section we present bounds on the proximity of k-connected triangulations for \(k \in \{3,4,5\}\) and k-connected quadrangulations for \(k \in \{2,3\}\). All bounds are sharp apart from an additive constant.

Our strategy is as follows: If G is a k-connected triangulation or quadrangulation, then we choose a central vertex v and derive certain properties of the sequence \(n_0(v), n_1(v), n_2(v), \ldots, n_r(v)\). These properties will be used to obtain a bound on the average distance of v, which in turn is a bound on the proximity of G. The following lemmata were proved in [1] (see the proofs of Theorems 2.7, 2.9 and 2.10 there).

Lemma 2.1. [1] Let G be a 3-connected plane graph of radius r with maximal face length \(\ell\). If v is a central vertex of G, then

(i) \[n_i(v) \geq 3\] for \(i \in \{1, 2, ..., \lfloor \frac{\ell}{2} \rfloor\} \cup \{r - \lfloor \frac{\ell}{2} \rfloor, r - \lfloor \frac{\ell}{2} \rfloor + 1, ..., r - 1\}\),
(ii) \(n_i(v) \geq 4\) for \(i \in \{\lfloor \frac{\ell}{2} \rfloor + 1, \lfloor \frac{\ell}{2} \rfloor + 2, ..., \ell\} \cup \{r - \ell, r - \ell + 1, ..., r - \lfloor \frac{\ell}{2} \rfloor - 1\}\),
(iii) \(n_i(v) \geq 6\) for \(i \in \{\ell + 1, \ell + 2, ..., r - \ell - 1\}\).

Lemma 2.2. [1] Let G be a 4-connected plane graph of radius r with maximal face length \(\ell\). If v is a central vertex of G, then

 \begin{array}{l} \mbox{(i) } n_i(v) \geq 4 \mbox{ for } i \in \{1, 2, \dots, \ell\} \cup \{r - \ell, r - \ell + 1, \dots, r - 1\}, \\ \mbox{(ii) } n_i(v) \geq 6 \mbox{ for } i \in \{\ell + 1, \ell + 2, \dots, \lfloor \frac{3\ell}{2} \rfloor\} \cup \{r - \lfloor \frac{3\ell}{2} \rfloor, r - \lfloor \frac{3\ell}{2} \rfloor + 1, \dots, r - \ell - 1\}, \\ \mbox{(iii) } n_i(v) \geq 8 \mbox{ for } i \in \{\lfloor \frac{3\ell}{2} \rfloor + 1, \lfloor \frac{3\ell}{2} \rfloor + 2, \dots, r - \lfloor \frac{3\ell}{2} \rfloor - 1\}. \end{array}

Lemma 2.3. [1] Let G be a 5-connected plane graph of radius r with maximal face length \(\ell\). If v is a central vertex of G, then

\begin{array}{l} (i) \ n_i(v) \geq 5 \ for \ i \in \{1,2,\dots,\ell\} \cup \{r-\ell,r-\ell+1,\dots,r-1\}, \\ (ii) \ n_i(v) \geq 6 \ for \ i \in \{\ell+1,\ell+2,\dots,\lfloor\frac{3\ell}{2}\rfloor\} \cup \{r-\lfloor\frac{3\ell}{2}\rfloor,r-\lfloor\frac{3\ell}{2}\rfloor+1,\dots,r-\ell-1\}, \\ (iii) \ n_i(v) \geq 8 \ for \ i \in \{\lfloor\frac{3\ell}{2}\rfloor+1,\lfloor\frac{3\ell}{2}\rfloor+2,\dots,2\ell\} \cup \{r-2\ell,r-2\ell+1,\dots,r-\lfloor\frac{3\ell}{2}\rfloor-1\}. \\ (iii) \ n_i(v) \geq 10 \ for \ i \in \{2\ell+1,2\ell+2,\dots,r-2\ell-1\}. \end{array}

We also need a corresponding result for 2-connected quadrangulations. The following two lemmata follow the approach in [1]. Given a fixed vertex v, we say that a vertex in \(N_i(v)\) is active if it has a neighbour in \(N_{i+1}(v)\). The set of active vertices in \(N_i(v)\) is denoted by \(A_i(v)\).

Lemma 2.4. Let G be a quadrangulation, v a vertex of G and \(i \in \mathbb{N}\) with \(1 \le i \le e(v) - 1\). For every active vertex \(w \in N_i(v)\) there exists another active vertex \(w' \in N_i(v)\) such that w and w' share a face of G.

Proof. Let u be an arbitrary vertex in \(A_i\). Since u is active, it has neighbours in \(N_{i-1}\) and in \(N_{i+1}\). Number the neighbours of u as \(x_0, x_1, \ldots, x_t\) such that the edges \(ux_j\) appear in clockwise order, \(x_0\) is in \(N_{i-1}\) and, say, \(x_k\) is in \(N_{i+1}\). Denote the face containing \(u, x_j, x_{j+1}\) and a fourth vertex by \(f_j\) for \(j = 0, 1, \ldots, t\), where subscripts are taken modulo t + 1, and let \(y_j\) be the vertex on \(f_j\) not equal to \(u, x_j\) and \(x_{j+1}\).

Consider the \((x_0, x_k)\)-walk \(W: x_0, y_0, x_1, y_1, \ldots, x_{k-1}, y_{k-1}x_k\). Since W joins a vertex in \(N_{i-1}\) to a vertex in \(N_{i+1}\), it contains a vertex in \(N_i\). Since G is bipartite, none of the neighbours of u is in \(N_i\), so there exists a vertex \(y_j\) which is in \(N_i\). We may assume that \(y_j\) is the last such vertex. Then \(y_j\) has a neighbour in \(N_{i+1}\) and is thus active. Since u and \(y_j\) share a face, Lemma 2.4 follows. \(\square\)

Lemma 2.5. Let G be a quadrangulation of order n and radius r. If v is a central vertex of G, then

(i) \[n_i \ge 2\] for \(i \in \{1, 2, r-2, r-1\}\), and

(ii) \[n_i > 4\] for \(i \in \{3, 4, \dots, r-3\}\).

Proof. Let v be a central vertex of the quadrangulation G and let \(i \in \{1, 2, ..., r-1\}\), where r is the radius of G.

• (i) Clearly, \(N_i\) contains an active vertex. It follows from Lemma 2.4 that every active vertex in \(N_i\) shares a face with some other active vertex in \(N_i\). Hence \(N_i\) contains at least two active vertices, and so (i) follows.
• (ii) Suppose to the contrary that (ii) does not hold. Then there exists \(i \in \{3, 4, ..., r-3\}\) such that \(n_i \leq 3\).

Denote the set of active vertices in \(N_i\) by \(A_i\). Since by Lemma 2.4 every vertex in \(A_i\) shares a face with some other vertex in \(A_i\), and since \(|A_i| \leq |N_i| = 3\), there exist a vertex \(z_i \in A_i\) that shares a face in G with every other vertices of \(A_i\). Since all faces of G have length G, it follows that \(d_G(z_i, y_i) \leq 2\) for all \(y_i \in A_i\). Let \(z_i \in N_i\) be a vertex on a shortest \((v, z_i)\)-path in G, so that \(d_G(z_i, z_i) = i - 3\).

We now bound \(d(z_3,x)\) for all \(x \in V(G)\). First let \(x \in \bigcup_{j=0}^{r-4} N_i\). Then \(d_G(z_3,x) \le d_G(z_3,v) + d_G(v,x) \le 3 + (r-4) = r-1\). Now let \(x \in \bigcup_{j=r-3}^r N_i\). Let \(x_i \in N_i\) be a vertex on a shortest (v,x)-path in G. Then \(x_i \in A_i\), and so \(d_G(z_i,x_i) \le 2\). Hence \(d_G(z_3,x) \le d_G(z_3,z_i) + d_G(z_i,x_i) + d_G(x_i,x) \le (i-3) + 2 + (r-i) = r-1\). So \(d_G(z_3,x) \le r-1\) in all cases, a contradiction to r being the radius of G. Hence our assumption \(n_i \le 3\) is false, and (ii) follows.

For the proofs below we define the function F which assigns to a finite sequence \(X=(x_0,x_1,\ldots,x_k)\) of integers the value \(F(X)=\sum_{i=0}^k ix_i\). So if v is a vertex of eccentricity r in a connected graph G, then \(\sigma(v)=\sum_{i=0}^r in_i(v)=F(n_0,n_1,\ldots,n_r)\).

Theorem 2.1. Let G be a planar graph of order n and v a central vertex of G. (a) If G is a triangulation, then

\[\pi(G) \le \frac{n+19}{12} + \frac{25}{3(n-1)}.\]

(b) If G is a 4-connected triangulation, then

\[\pi(G) \le \frac{n+35}{16} + \frac{91}{4(n-1)}.\]

(c) If G is a 5-connected triangulation, then

\[\pi(G) \le \frac{n+57}{20} + \frac{393}{10(n-1)}.\]

(d) If G is a quadrangulation, then

\[\pi(G) \le \frac{n+11}{8} + \frac{9}{2(n-1)}.\]

(e) If G is a 3-connected quadrangulation, then

\[\pi(G) \le \frac{n+25}{12} + \frac{169}{12(n-1)}.\]

Proof. We only prove part (a) of the theorem; the proofs of (b)-(e) are analogous. Let G be a simple triangulation, let r be its radius and let v be a central vertex of G. It suffices to prove that

\[\sigma(v) \le \frac{1}{12}(n^2 + 18n + 81).\]

Let \(n_i := n_i(v)\) for i = 0, 1, ..., r. Then \(\sigma(v) = \sum_{i=1}^r i n_i = F(n_0, n_1, ..., n_r)\). By Lemma 2.1, we have \(n_1, n_{r-1} \ge 3\), \(n_2, n_3, n_{r-3}, n_{r-2} \ge 4\), and \(n_i \ge 6\) for i = 4, 5, ..., r-4. Moreover, we have \(n_0 = 1\), \(n_r \ge 1\), and \(\sum_{i=0}^r n_i = n\).

Now assume that for given n the integers \(r', n'_0, n'_1, \ldots, n'_{r'}\) are chosen to maximise \(F(n'_0, n'_1, \ldots, n'_{r'})\) subject to the above conditions (with \(n_i\) and r replaced by \(n'_i\) and r', respectively). Then clearly \(n'_0 = 1, n'_1 = 3, n'_2 = n'_3 = 4, n'_i = 6\) for \(i = 4, 5, \ldots, r' - 4\), and \(n'_{r'-3} = n'_{r'-2} = 4, n'_{r'-1} = 3\).

Consider the sequence \(X^* = (n'_0, n'_1, \dots, n'_{r'-1}, 1)\). The sum of the entries of \(X^*\) is \(n - n_{r'} + 1\). Simple calculations show that \(r' = \frac{1}{6}(n - n'_{r'} + 19)\) and \(F(X^*) = \frac{1}{2}r'(n - n'_{r'} + 1)\). Hence

\[F(n'_0, n'_1, \dots, n'_{r'}) = F(X^*) + r'(n'_{r'} - 1) = \frac{1}{2}r'(n + n'_{r'} - 1).\]

Substituting \(r' = \frac{1}{6}(n - n'_{r'} + 19)\) yields, after simplification, \(F(n'_0, n'_1, \dots, n'_{r'}) = \frac{1}{12}(n^2 + 18n - (n'_{r'})^2 + 20n'_{r'} - 19)\). Since the function \(-x^2 + 20x\) attains its maximum 100 for x = 10, we have \(-(n'_{r'})^2 + 20n'_{r'} \le 100\), and so we get \(F(n'_0, n'_1, \dots, n'_{r'}) \le \frac{1}{12}(n^2 + 18n + 81)\) and thus

\[\sigma(v) = F(n_0, n_1, \dots, n_r) \le F(n'_0, n'_1, \dots, n'_{r'}) \le \frac{1}{12}(n^2 + 18n + 81),\]

as desired. \(\Box\)

The bounds in Theorem 2.1 appear not to be sharp. The graphs constructed in the following section show that the bounds are sharp up to an additive constant.

3. Computational Results

This section includes figures of the extremal structures which minimize the status given certain connectivity. Additionally, formulae and tables summarize these minimized values. This paper heavily utilized a software package called Plantri, we are grateful for their hard work and dedication to the exploration of planar graphs. For each category of problem (triangulations, 4-connected triangulations, 5-connected triangulations, quadrangulations and 3-connected quadrangulations) there is a function (see formulae (1), (2), (3), (4), and (5)), which states the minimum status of the structures, along with a table, which summarizes the largest minimum status found for a given order in that category and a "Count", summarizing how many graphs attain the optimal value. (Recall that the minimum status is defined by \((n-1)\pi(G)\).) We use the minimum status rather than

the proximity in the tables to remain in the domain of integers. If any Table entry displays a dash, there exists no graphs in that category on the given number of vertices. We searched the same number of isomorphism classes as [7], [8], [9], [18], [21], verifying that our values are in fact optimal. In each figure below, red edges represent the repeating pattern and the black node marks one of the vertices which minimizes the status in that graph and likely maximizes the proximity within the category defined by order and connectivity. Due to fact that few congruence classes of a large modulus fall into the range, where we can do exhaustive calculations, finding a repeating pattern was difficult by brute force calculations. Once a pattern was established, extensive sampling was conducted in order to test if a better structure could be found, but no such structure ever arose. We conjecture that the bounds presented in this section are optimal.

Figure 1. A triangulation Tⁿ on n = 6k vertices which is conjectured to maximize the proximity among triangulations of this order.

Figure 2. A triangulation Tⁿ on n = 6k + 1 vertices which is conjectured to maximize the proximity among triangulations of this order.

Figure 3. A triangulation Tⁿ on n = 6k + 2 vertices which is conjectured to maximize the proximity among triangulations of this order.

Figure 4. A triangulation Tⁿ on n = 6k + 3 vertices which is conjectured to maximize the proximity among triangulations of this order.

Figure 5. A triangulation Tⁿ on n = 6k + 4 vertices which is conjectured to maximize the proximity among triangulations of this order.

Figure 6. A triangulation Tⁿ on n = 6k + 5 vertices which is conjectured to maximize the proximity among triangulations of this order.

Table 1. A summary of the largest minimum status among all triangulations.

\[\pi(T_n) = \begin{cases} \frac{n+5}{12} + \frac{5}{12(n-1)} & \text{if } n = 6k \\ \frac{n+5}{12} & \text{if } n = 6k+1 \\ \frac{n+5}{12} + \frac{5}{12(n-1)} & \text{if } n = 6k+2 \\ \frac{n+5}{12} + \frac{2}{3(n-1)} & \text{if } n = 6k+3 \\ \frac{n+5}{12} + \frac{3}{4(n-1)} & \text{if } n = 6k+4 \\ \frac{n+5}{12} + \frac{2}{3(n-1)} & \text{if } n = 6k+5 \end{cases}\] \[(1)\]

Figure 7. A 4-connected triangulation T 4 ⁿ on n = 8k + 2 vertices which is conjectured to maximize the proximity among triangulations of this order and connectivity.

Figure 8. A 4-connected triangulation T 4 ⁿ on n = 8k + 3 vertices which is conjectured to maximize the proximity among triangulations of this order and connectivity.

Figure 9. A 4-connected triangulation T 4 ⁿ on n = 8k + 4 vertices which is conjectured to maximize the proximity among triangulations of this order and connectivity.

Figure 10. A 4-connected triangulation T 4 ⁿ on n = 8k + 5 vertices which is conjectured to maximize the proximity among triangulations of this order and connectivity.

Figure 11. A 4-connected triangulation T 4 ⁿ on n = 8k + 6 vertices which is conjectured to maximize the proximity among triangulations of this order and connectivity.

Figure 12. A 4-connected triangulation T 4 ⁿ on n = 8k + 7 vertices which is conjectured to maximize the proximity among triangulations of this order and connectivity.

Figure 13. A 4-connected triangulation T 4 ⁿ on n = 8k vertices which is conjectured to maximize the proximity among triangulations of this order and connectivity.

Figure 14. A 4-connected triangulation T 4 ⁿ on n = 8k + 1 vertices which is conjectured to maximize the proximity among triangulations of this order and connectivity.

Table 2. A summary of the largest minimum status among all 4-connected triangulations.

\[\pi(T_n^4) = \begin{cases} \frac{n+9}{16} + \frac{21}{16(n-1)} & \text{if } n = 8k+2\\ \frac{n+9}{16} + \frac{3}{2(n-1)} & \text{if } n = 8k+3\\ \frac{n+9}{16} + \frac{25}{16(n-1)} & \text{if } n = 8k+4\\ \frac{n+9}{16} + \frac{3}{2(n-1)} & \text{if } n = 8k+5\\ \frac{n+9}{16} + \frac{21}{16(n-1)} & \text{if } n = 8k+6\\ \frac{n+9}{16} + \frac{1}{n-1} & \text{if } n = 8k+7\\ \frac{n+9}{16} + \frac{25}{16(n-1)} & \text{if } n = 8k\\ \frac{n+9}{16} + \frac{1}{n-1} & \text{if } n = 8k\\ \frac{n+9}{16} + \frac{1}{n-1} & \text{if } n = 8k+1 \end{cases}\] \[(2)\]

Figure 15. A 5-connected triangulation T 5 ⁿ on n = 10k + 7 vertices which is conjectured to maximize the proximity among triangulations of this order and connectivity.

Figure 16. A 5-connected triangulation T 5 ⁿ on n = 10k + 8 vertices which is conjectured to maximize the proximity among triangulations of this order and connectivity. Here, the orange pattern is to be repeated twice rather than once.

Figure 17. A 5-connected triangulation T 5 ⁿ on n = 10k + 9 vertices which is conjectured to maximize the proximity among triangulations of this order and connectivity.

Figure 18. A 5-connected triangulation T 5 ⁿ on n = 10k vertices which is conjectured to maximize the proximity among triangulations of this order and connectivity.

Figure 19. A 5-connected triangulation T 5 ⁿ on n = 10k + 1 vertices which is conjectured to maximize the proximity among triangulations of this order and connectivity.

Figure 20. A 5-connected triangulation T 5 ⁿ on n = 10k + 2 vertices which is conjectured to maximize the proximity among triangulations of this order and connectivity.

Figure 21. A 5-connected triangulation T 5 ⁿ on n = 10k + 3 vertices which is conjectured to maximize the proximity among triangulations of this order and connectivity.

Figure 22. A 5-connected triangulation T 5 ⁿ on n = 10k + 4 vertices which is conjectured to maximize the proximity among triangulations of this order and connectivity.

Figure 23. A 5-connected triangulation T 5 ⁿ on n = 10k + 5 vertices which is conjectured to maximize the proximity among triangulations of this order and connectivity.

Figure 24. A 5-connected triangulation T ⁿ on n = 10k + 6 vertices which is conjectured to maximize the proximity among triangulations of this order and connectivity.

Table 3. A summary of the largest minimum status among all 5-connected triangulations.

Proximity in triangulations and quadrangulations | Eva Czabarka et al. ´

\[\pi(T_n^5) = \begin{cases} \frac{n+13}{20} & \text{if } n = 10k+7\\ \frac{n+13}{20} - \frac{7}{20(n-1)} & \text{if } n = 10k+8\\ \frac{n+13}{20} - \frac{4}{5(n-1)} & \text{if } n = 10k+9\\ \frac{n+13}{20} - \frac{7}{20(n-1)} & \text{if } n = 10k\\ \frac{n+13}{20} - \frac{1}{n-1} & \text{if } n = 10k+1\\ \frac{n+13}{20} - \frac{1}{4(n-1)} & \text{if } n = 10k+2\\ \frac{n+13}{20} - \frac{8}{5(n-1)} & \text{if } n = 10k+3\\ \frac{n+13}{20} - \frac{1}{20(n-1)} & \text{if } n = 10k+4\\ \frac{n+13}{20} - \frac{3}{5(n-1)} & \text{if } n = 10k+5\\ \frac{n+13}{20} - \frac{3}{4(n-1)} & \text{if } n = 10k+6 \end{cases}\] \[(3)\]

Figure 25. A quadrangulation Qⁿ on n = 4k vertices which is conjectured to maximize the proximity among quadrangulations of this order.

Figure 26. A quadrangulation Qⁿ on n = 4k + 1 vertices which is conjectured to maximize the proximity among quadrangulations of this order.

\[\pi(Q_n) = \begin{cases} \frac{n+1}{8} + \frac{17}{8(n-1)} & \text{if } n = 4k\\ \frac{n+1}{8} + \frac{2}{n-1} & \text{if } n = 4k+1\\ \frac{n+1}{8} + \frac{21}{8(n-1)} & \text{if } n = 4k+2\\ \frac{n+1}{8} + \frac{2}{n-1} & \text{if } n = 4k+3 \end{cases}\] \[(4)\]

Figure 27. A quadrangulation Qⁿ on n = 4k + 2 vertices which is conjectured to maximize the proximity among quadrangulations of this order.

Figure 28. A quadrangulation Qⁿ on n = 4k + 3 vertices which is conjectured to maximize the proximity among quadrangulations of this order.

Table 4. A summary of the largest minimum status among all quadrangulations.

Figure 29. A 3-connected quadrangulation Q^{3 n} on n = 6k+ 2 vertices which is conjectured to maximize the proximity among quadrangulations of this order and connectivity.

Figure 30. A 3-connected quadrangulation Q^{3 n} on n = 6k+ 3 vertices which is conjectured to maximize the proximity among quadrangulations of this order and connectivity.

Figure 31. A 3-connected quadrangulation Q^{3 n} on n = 6k+ 4 vertices which is conjectured to maximize the proximity among quadrangulations of this order and connectivity.

Figure 32. A 3-connected quadrangulation Q^{3 n} on n = 6k+ 5 vertices which is conjectured to maximize the proximity among quadrangulations of this order and connectivity.

Figure 33. A 3-connected quadrangulation Q^{3 n} on n = 6k vertices which is conjectured to maximize the proximity.

Figure 34. A 3-connected quadrangulation Q^{3 n} on n = 6k+ 1 vertices which is conjectured to maximize the proximity among quadrangulations of this order and connectivity.

\[\pi(Q_n^3) = \begin{cases} \frac{n+9}{12} - \frac{23}{12(n-1)} & \text{if } n = 6k+2\\ \frac{n+9}{12} - \frac{4}{n-1} & \text{if } n = 6k+3\\ \frac{n+9}{12} - \frac{13}{4(n-1)} & \text{if } n = 6k+4\\ \frac{n+9}{12} - \frac{8}{3(n-1)} & \text{if } n = 6k+5\\ \frac{n+9}{12} - \frac{13}{4(n-1)} & \text{if } n = 6k\\ \frac{n+9}{12} - \frac{3}{n-1} & \text{if } n = 6k+1 \end{cases}\] \[(5)\]

Acknowledgement

The second author was supported in part by the National Research Foundation of South Africa, grant number 118521, the third and fourth authors were supported by the NSF DMS, grant number 1600811.

Table 5. A summary of the largest minimum status among all 3-connected quadrangulations.

References

• [1] P. Ali, P. Dankelmann, S. Mukwembi, The radius of k-connected planar graphs with bounded faces. Discrete Appl. Math. 312 (2012), 3636–3642.
• [2] P. Ali, P. Dankelmann, M.J. Morgan, S. Mukwembi, H.C. Swart, T. Vetr´ık (2018). The average eccentricity, spanning trees of plane graphs, size and order. Utilitas Math 107 (2018), 37–49.
• [3] Aouchiche, M.; Caporossi, G.; Hansen, P.; Variable Neighbourhood Search for Extremal Graphs, 20 Automated Comparison of Graph Invariants. MATCH Commun. Math. Comput. Chem. 58 (2007), 365–384.
• [4] Aouchiche, M.; Hansen, P.; Nordhaus-Gaddum relations for proximity and remoteness in graphs. Comput. Math. Appl. 59 (8) (2010), 2827–2835.
• [5] M. Aouchiche, P. Hansen, Proximity and remoteness in graphs: results and conjectures. Networks 58 (2) (2011), 95–102.
• [6] Barefoot, C.A.; Entringer, R.C.; Szekely, L.A.; Extremal values for ratios of distances in ´ trees. Discrete Appl. Math. 80 (1997), 37–56.
• [7] R. Bowen and S. Fisk, Generation of Triangulations of the Sphere. Math. Comp. 21 (1967), 250–252.
• [8] G. Brinkmann, S. Greenberg, C. Greenhill, B.D. McKay, R. Thomas, P. Wollan, Generation of simple quadrangulations of the sphere. Discrete Math. 305 (1) (2005), 33–54.
• [9] G. Brinkmann and B. McKay Construction of planar triangulations with minimum degree 5. Disc. Math. 301 (2005), 147–163.
• [10] Z. Che, K.L. Collins, An upper bound on Wiener indices of maximal planar graphs. Discrete Appl. Math. 258 (2019), 76–86.
• [11] E. Czabarka, P. Dankelmann, T. Olsen and L. A. Sz ´ ekely, Wiener Index and Remoteness ´ in Triangulations and Quadrangulations. Discrete Mathematics & Theoretical Computer Science 23 (1) (2021)
• [12] P. Dankelmann, Proximity, remoteness, and minimum degree. Discrete Appl. Math. 184 (2015), 223–228.
• [13] P. Dankelmann, New bounds on proximity and remoteness in graphs. Communications in Combinatorics and Optimization 1 (1) (2016), 28–40.
• [14] J..K. Doyle, J.E. Graver, Mean distance in a graph. Discrete Math. 7 (1977), 147–154.
• [15] R.C. Entringer, D.E. Jackson, D.A. Snyder, Distance in graphs. Czech Math. J. 26 (1976), 283–296.

• [16] D. Ghosh, E. Gyori, A. Paulos, N. Salia, O. Zamora, The Maximum Wiener Index of Maximal ˝ Planar Graphs. Journal of Combinatorial Optimization 40 (2020), 1121—1135.
• [17] E. Gyori, A. Paulos, C. Xiao, Wiener Index of Quadrangulation Graphs. ˝ Discrete Applied Mathematics 289 (2021), 262–269.
• [18] F. Lutz. Enumeration and random realization of triangulated surfaces. Discrete Diff. Geo. OWS 38 (2008), 235–253.
• [19] Ma, B.; Wu, B.; Zhang, W.; Proximity and average eccentricity of a graph. Inform. Process. Lett. 112 (10) (2012), 392–395.
• [20] G. I. Miller. Finding small cycle separators for 2-connected planar graphs. J. Comput. Sys. Sci. 32 (3) (1986), 265–279.
• [21] 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.
• [22] Wu, B.; Zhang, W.; Average distance, radius and remoteness of a graph. Ars Math. Contemp. 7 (2014), 441–452.
• [23] B. Zelinka, Medians and peripherians of trees. Arch. Math. (Brno) 4 (1968), 87–95.