Printer Friendly

Wiener Index and Remoteness in Triangulations and Quadrangulations.

1 Definitions and Selected Results on the Wiener Index

Let G be a connected graph. The Wiener index W(G) of G is the sum of the distances between all unordered pairs of distinct vertices, i. e.,

[mathematical expression not reproducible]

where [d.sub.G](u, v) is the usual distance between vertices u and v, i.e., the minimum number of edges on a (u, v)-path in G. The Wiener index was first studied by the chemist Wiener [41], who observed that it relates well to the boiling point of certain alkanes. Several other applications in chemistry were found subsequently, see for example [35].

The systematic study of the mathematical properties of the Wiener index began with the classical papers by Doyle and Graver [18], Entringer, Jackson and Snyder [19] and Plesnik [34]. Several bounds on the Wiener index and closely related parameters, such as transmission or routing cost (defined as the sum of the distances between all ordered pairs of vertices), average distance or mean distance (both are defined as the arithmetic mean of the distances between all unordered pairs of distinct vertices) have been proved since.

The most basic upper bound on W(G) states that if G is a connected graph of order n, then

[mathematical expression not reproducible] (1)

which is attained only by paths (see [18] [34], [30]). Many sharp or asymptotically sharp bounds on W(G) in terms of other graph parameters are known, for example minimum degree ([4], [11], [28]), connectivity ([14], [21]), edge-connectivity ([12], [13]) and maximum degree [20]. For recent results on the Wiener index see, for example, [17], [23], [25], [26], [27] [29], [33], [39], [38] and [40].

Entringer et al. [19] found that among trees on the same number of vertices, the star minimizes and the path maximizes the Wiener index (see also [30] problem 6.23). Fischermann, Hoffmann, Rauten-bach, Szekely and Volkmann [20] (see also [24]) characterized binary trees with minimum and maximum Wiener index.

The notation we use in this paper is as follows. If G is a graph, then we denote its vertex set and edge set by V(G) and E(G). By n(G) and m(G) we mean the order and size of G, defined as |V(G)| and |E(G)|, respectively. The eccentricity e(v) of a vertex v is the distance to a vertex farthest from v, i.e., e(v) = [max.sub.u[member of]V(G)] [d.sub.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 neighborhood of a vertex v of G is the set of vertices adjacent to v, it is denoted by [N.sub.G](v), and the cardinality |[N.sub.G](v)| is the degree of v, which we denote by [deg.sub.G](v). If i is an integer with 0 [less than or equal to] i [less than or equal to] e(v), then [N.sub.i](v) denotes the set of all vertices at distance exactly i from v, and we write [n.sub.i](v) for \Ni(v)\. If there is no danger of confusion, we often omit the subscript G or the argument G or v. If A, B C V(G), then m(A, B) denotes the number of edges that join a vertex in A to a vertex in B, and G[A] denotes the subgraph of G induced by A. If w is a vertex of G and A [[subset].bar] V(G), then a (w, A)-fan is a set of |A| paths from w to A, where any two paths have only w in common. If G is connected and not complete, then the connectivity of G, [kappa](G), is the smallest number of vertices whose deletion renders G disconnected. The (not necessarily simple) plane graph G is a triangulation (resp. quadrangulation) if every face is a triangle (resp. 4-cycle). A simple triangulation (resp. simple quadrangulation) is a triangulation (resp. quadrangulation) whose underlying graph is simple. i.e. has no multiple edges. The graph H is a minor of the graph G, if H can be obtained from a subgraph of G by edge-contractions.

By [C.sub.n], [K.sub.n] and [K.sub.n] we mean the cycle, the complete graph, and the edgeless graph on n vertices, respectively. If G and H are graphs then G + H denotes the graph obtained from the union of G and H by adding edges joining every vertex of G to every vertex of H.

2 Summary of the Results in this Paper

Another natural class of study for extremal Wiener index is planar graphs. However, as the maximum Wiener index of graphs (1) is attained by a path, it makes sense to consider more restricted classes of planar graphs, like simple triangulations and quadrangulations. Che and Collins [8], and the authors of the present paper [9] investigated independently the maximum Wiener index of triangulations and presented the same simple triangulation of order n (see Figures 5, 6, 7) with Wiener index

[mathematical expression not reproducible] (2)

which they conjectured to be optimal. (Note that this sequence is present in the On-Line Encyclopedia of Integer Sequences [37] under A014125, which is the bisection of A001400. The displayed closed form is due to Bruno Berseli [37].) We [9] announced that this conjecture is asymptotically true before the paper [8] was submitted. Che and Collins [8] verified this conjecture for simple triangulations of order not exceeding 10. Using computer, we verified this conjecture for simple triangulations of order not exceeding 18, see Table 1 in [10], an earlier version of this paper. Very recently, Debarun Ghosh, Ervin Gyori, Addisu Paulos, Nika Salia, Oscar Zamora verified this conjecture [22].

In this paper we prove a generalization of this conjecture asymptotically. Note that every simple triangulation is 3-connected, but a simple triangulation cannot be 6-connected because of the number of edges. Our main theorem (Theorem 2) proves that for any 3 [less than or equal to] [kappa] [less than or equal to] 5, the Wiener index of any [kappa]-connected simple triangulation of order n is at most [mathematical expression not reproducible]. We also prove in Theorem 3 that for any 2 [less than or equal to] [kappa] [less than or equal to] 3, the Wiener index of any [kappa]-connected simple quadrangulation of order n is at most [mathematical expression not reproducible].

We provide constructions matching the upper bounds of Theorems 2 and 3 for the maximum Wiener index of triangulations and quadrangulations of given connectivity. We do more, as we exhibit triangulations and quadrangulations following patterns by the residue of the order n modulo [kappa], which we conjecture as realizers of the maximum Wiener index. Our conjectures are based on extensive computations. We detail next these conjectures.

We constructed 4-connected simple triangulations with Wiener index

[mathematical expression not reproducible] (3)

see Figures 8, 9, 10, 11. This proves that Theorem 2 is also asymptotically tight for [kappa] = 4. Furthermore, we conjecture that the repetition of the obvious pattern in these figures provide the extremal triangulations. Using computer, we verified this conjecture for simple triangulations of order not exceeding 22, see Table 2.

We constructed 5-connected simple triangulations with Wiener index

[mathematical expression not reproducible] (4)

see Figures 12, 13, 15, 16, 17. This proves that Theorem 2 is also asymptotically tight for [kappa] = 5. Furthermore, we conjecture that the repetition of the obvious pattern in these figures provide the extremal triangulations. We arrived to these conjectures using computer and also guesswork regarding the pattern. Therefore these conjectures for the 5-connected case are less supported with computational evidence than other conjectures in this paper, as we were able to do the computation only up to the order 32, see Table 3. The issue is that the pattern slowly develops, and orders following the same pattern differ by 5--therefore we do not have sufficiently many data points to have a very convincing conjecture.

We are indebted to Paul Kainen, who after hearing about our triangulation results, asked whether we can prove similar results for simple quadrangulations. Recall that any simple quadrangulation is 2-connected, but no simple quadrangulation is 4-connected. We conjecture that the maximum Wiener index of a simple quadrangulation of order n is

[mathematical expression not reproducible] (5)

based on Figures 18, 19. Furthermore, we conjecture that the repetition of the obvious pattern in these figures provide the extremal quadrangulations. Using computer, we verified this conjecture for simple quadrangulations of order not exceeding 20, see Table 4.

We conjecture that the maximum Wiener index of a 3-connected simple quadrangulation of order n is

[mathematical expression not reproducible] (6)

based on Figures 20, 21,22. Furthermore, we conjecture that the repetition of the obvious pattern in these figures provide the extremal quadrangulations. Using computer, we verified this conjecture for simple quadrangulations of order not exceeding 28, see Table 5.

Section 5 contains the conjectures stated so far in the form of drawings for some fixed order, but with emphasis on the general pattern: the red colored part is the repeated pattern. Even more, we conjecture based on computational evidence that those drawings not only provide the maximum Wiener index, but for sufficiently large n they are unique with this property.

We remark here that the result of [22] described by formula (2) does not hold for non-simple triangulations. For the construction of non-simple triangulations with asymptotically larger Wiener indices, see Figure 1. In fact, we conjecture that these constructions are optimal for non-simple triangulations. The non-simple quadrangulation on Figure 2 has a larger Wiener index than conjectured best simple quadrangulation on Figure 18, but difference is not in the leading term. For the rest of the paper, under the terms triangulation and quadrangulation we will always understand simple triangulation and quadrangulation.

Che and Collins noted [8] that the minimum Wiener index of a triangulation of order n is a trivial problem, as Euler's formula determines the number of edges, and there are constructions, in which every pair of vertices are at most distance two. The situation is analogous for quadrangulations. For minimizers, see Figure 3.

There is second research direction of this paper, in addition to the Wiener index. We give bounds on the total distance [sigma](v) and the average distance [sigma](v) of a vertex v, defined as the sum and the average, respectively, of the distances from v to all other vertices. Bounds on [sigma](v) were obtained, for example, in [3] [19] and [43]. Of particular interest is the maximum value over all v G V(G) of[sigma](v) in a graph G, usually referred to as the remoteness [rho](G), of G. It was shown by Zelinka [43] and, independently, by Aouchiche and Hansen [2] that the remoteness is at most n/2. For graphs of given minimum degree [delta] these bounds were improved in [15] by a factor of about 3/[delta]+1. For more recent results on remoteness see, for example, [16], and [42].

In this paper we give sharp upper bounds on remoteness of triangulations and quadrangulations with given connectivity in Corollary 1 and Proposition 2. The bounds are sharp in Proposition 2 and Corollary 1 by Figures 5 through 12 and Figures 14 through 22. It is not difficult to compute the distances on those figures from the black vertex to the remaining vertices and show that the sum of distances from the black vertex meets the upper bound for remoteness. Details will be provided in the Ph.D. dissertation of the third author. Our results show that the maximum remoteness among triangulations and quadrangulations of prescribed connectivity [kappa] is achieved on those ones that are conjectured to maximize the Wiener index, except for 5-connected triangulations of order n = 5k + 3. There are, however, lots of different realizations of the maximum of remoteness in all classes that we investigate, except among quadrangulations.

3 Upper Bounds on the Remoteness of Triangulations and Quadrangulations

In this section we present bounds on the remoteness of triangulations and quadrangulations. A sharp upper bound on the remoteness of a triangulation of given order was given by Che and Collins [8]. We give corresponding bounds for 4-connected and 5-connected triangulations, as well as for 2-connected and 3-connected quadrangulations.

We begin by stating a sharp bound on the distance of an arbitrary vertex in a [kappa]-connected graph of given order due to Favaron, Kouider and Maheo [21], from which we will derive some of our bounds.

Proposition 1. [21] Let G be a [kappa]-connected graph of order n, and x an arbitrary vertex of G. Then

[mathematical expression not reproducible]

Every simple triangulation is 3-connected, and every simple quadrangulation is 2-connected. Proposition 1 yields thus the following sharp bounds for the remoteness of 3-connected and 4-connected triangulations and 2-connected quadrangulations.

Corollary 1. (a) [8] If G is a simple triangulation of order n, then

[mathematical expression not reproducible]

where [[epsilon].sub.n] = 0 ifn = 1 (mod 3), and [mathematical expression not reproducible] if n = 0,2 (mod 3).

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

[mathematical expression not reproducible]

where [[epsilon].sub.n] = 0 ifn = 1 (mod 4), [mathematical expression not reproducible] if n [equivalent to] 0, 2 (mod 4), and [mathematical expression not reproducible] if n [equivalent to] 3 (mod 4).

(c) If G is a simple quadrangulation of order n, then

[mathematical expression not reproducible]

where [[epsilon].sub.n] = 0 if n [equivalent to] 1 (mod 2), and [mathematical expression not reproducible] if n = 0 (mod 2). []

Proposition 1 also yields good bounds for the remoteness of 5-connected triangulations and 3-connected quadrangulations. These bounds are however not sharp for all values of n. In order to obtain sharp bounds we need some additional terminology and results from [1].

Let v be a fixed vertex of a connected plane graph and i [member of] N with i < e(v). We say that a vertex w [member of] [N.sub.i](v) is active if it has a neighbor in [N.sub.i+1](v).

Lemma 1. [1] Let G be a 3-connected plane graph, v a vertex of G and i [member of] N with 1 < i < e(v) - 1. For every active vertex w [member of] [N.sub.i](v) there exist two other active vertices w', w" [member of] [N.sub.i](v) such that w and w' share a face of G, and w and w" also share a face of G.

Lemma 2. (a)Let G be a 5-connected simple triangulation, v a vertex of G and d= [e.sub.G](v). If [n.sub.d-1](v) = 5, then [n.sub.d](v) = 1.

(b) Let G be a 3-connected simple quadrangulation, v a vertex of G and d = [e.sub.G](v). If [n.sub.d-1](v) = 3, then [n.sub.d](v) = 1. If [n.sub.d-2](v) = 3 and [n.sub.d-1](v) = 4, then [n.sub.d](v) > 1.

Proof: (a) Assume that G is a 5-connected simple triangulation, v is a vertex of G, and [n.sub.d-1] = 5, where d is the eccentricity of v. This implies that [N.sub.d-1] is a minimum cutset of G. Hence, since G is a triangulation, [N.sub.d-1] induces a cycle C of length 5. We first show that

the vertices in [N.sub.d] are all inside C, or all outside C. (7)

Suppose not. Then there exist vertices a, b [member of] [N.sub.d] such that a is inside C, and b is outside C. Since G is 5-connected, there exist a (v, [N.sub.d-1])-fan [F.sub.v], an (a, [N.sub.d-1])-fan [F.sub.a], and a (b, [N.sub.d-1])-fan [F.sub.b]. Any two of these three fans share only the vertices of [N.sub.d-1]. Indeed, other than vertices in [N.sub.d-1,] fan [F.sub.v] contains only vertices in [mathematical expression not reproducible] [N.sub.i], while fan [F.sub.a] contains only vertices in [N.sub.d-1] [union] [N.sub.d] that are inside C, while fan [F.sub.b] contains only vertices in [N.sub.d-1] [union] [N.sub.d] that are outside C. Now contracting the edges in [F.sub.a] - [N.sub.d-1], the edges in [F.sub.b] - [N.sub.d-1] and the edges in [F.sub.v] - [N.sub.d-1] to three single vertices yields a graph that contains 3[K.sub.1] + [C.sub.5] as a subgraph. Hence G contains 3[K.sub.1] + [C.sub.5] as a minor. Contracting three consecutive vertices of the 5-cycle shows that this implies that G contains [K.sub.3] + 3[K.sub.1] as a minor, which contradicts the planarity of G. This contradiction proves (7).

By (7) we may assume that all vertices of [N.sub.d] are inside the cycle C. Since every vertex of [N.sub.d] is adjacent to some vertex of [N.sub.d-1,] the subgraph G[[N.sub.d]] is outerplanar. Hence

[mathematical expression not reproducible] (8)

We now bound the sum of the degrees of the vertices in [N.sub.d]. Let H be the plane graph obtained from G [[N.sub.d-1] [union] [N.sub.d]] by adding a new vertex z in the outer face of C and joining it to all five vertices of C. Then H has order n(H) = 1 + [n.sub.d-1] + [n.sub.d] = [n.sub.d] + 6. Since H is a plane graph we have m(H) [less than or equal to] 3n(H) - 6 [less than or equal to] 3[n.sub.d] + 12. At least 10 edges of H are incident with z or belong to C, and are thus not incident with any vertex of [N.sub.d], so they don't contribute to the sum of the degrees of vertices in [N.sub.d]. Since the edges of G[[N.sub.d]] contribute two to the sum of the degrees of vertices in [N.sub.d], we have

[mathematical expression not reproducible]

It is easy to verify that this implies [mathematical expression not reproducible] whenever [n.sub.d] > 1. But since G is 5-connected, every vertex of G has degree at least five.Hence we conclude that [n.sub.d] = 1, which proves (a).

(b) Let G be a 3-connected simple quadrangulation, v a vertex of G, and d = e(v). To prove the first statement assume that [n.sub.d-1] = 3. Let [N.sub.d-1](v) = {w, w', w"}. Since G is a quadrangulation and thus bipartite, the set {w, w, w"} is independent in G. Since G is 3-connected, the vertices w, w', w" have a neighbor in [N.sub.d] and are thus active. By Lemma 1, w and w' share a face, and so do w and w", as well as w' and w". Hence we can add edges ww', ww" and ww" to G to obtain a plane graph (but not a quadrangulation). Let C be the cycle consisting of the edges ww', w'w", w"w. A proof similar to that in (a) shows that the vertices of [N.sub.d] are all inside C, or all outside C. Without loss of generality we assume the former. We now bound the sum of the degrees of the vertices in [N.sub.d].

Let H be the plane graph obtained from G[[N.sub.d-1] [union] [N.sub.d]] + E(C) by adding a new vertex z in the outer face of C and joining it to all three vertices of C. Since G is a quadrangulation, the only faces of H of length three are the six faces that have one of the three edges of C on their boundary. Let H' be the plane graph H - E(C) = G[[N.sub.d-1] [union] [N.sub.d]]. Then n(H') = [n.sub.d-1] + [n.sub.d] + 1 = [n.sub.d] + 4 and, since H' has only faces of length at least four, m(H') [less than or equal to] 2n(H') - 4 = 2[n.sub.d] + 4.

Exactly three edges of H are incident with z and are thus not incident with any vertex of [N.sub.d]. Since G is bipartite, G[[N.sub.d]] contains no edges. Hence

[mathematical expression not reproducible]

This implies [mathematical expression not reproducible] [deg.sub.G](x) < 3[n.sub.d] whenever [n.sub.d] > 1. But since G is 3-connected, every vertex of G has degree at least three. Hence we conclude that [n.sub.d] = 1, which proves the first statement of (b). To prove the second statement of (b) assume that [n.sub.d-2] = 3 and [n.sub.d-1] = 4. Suppose to the contrary that [n.sub.d] = 1. Let [N.sub.d-2] = {w,w, w"}. The same arguments as in the proof of the first statement of (b) show that we can add the edges ww', ww", w'w" to G to obtain a plane graph, such that these three edges form a cycle C, and that the vertices in [N.sub.d-1] [union] [N.sub.d] are either all inside C or all outside C, without loss of generality we assume the former. Let H be the plane graph obtained from G[[N.sub.d-2] [union][N.sub.d-1] [union] [N.sub.d]] + E(C) by adding a new vertex z in the outer face of C and joining it to all three vertices of C. Since G is a quadrangulation, the only faces of H of length three are the six faces that have one of the three edges of C on their boundary. Let H' be the plane graph H - E(C) = G[[N.sub.d-2] [union] [N.sub.d-1] [union] [N.sub.d]]. Then n(H') = [n.sub.d-2] + [n.sub.d-1] + [n.sub.d] + 1 = 9 and, since H' has only faces of length at least four, m(H') [less than or equal to] 2n(H')-4 = 14. Exactly three edges of H' are incident with z and thus not incident with vertices in [N.sub.d-1]. Since G is bipartite, no edge joins two vertices of [N.sub.d-1], and so we have [mathematical expression not reproducible](x) [less than or equal to] 11 < 3[n.sub.d-1]. Therefore, [N.sub.d-1] contains a vertex of degree less than three in G, which contradicts G being 3-connected. The second statement of (b) follows. []

For the remaining proof of this section we define the function F which assigns to a finite sequence

X = ([x.sub.0], [x.sub.1],..., [x.sub.k]) of integers the value [mathematical expression not reproducible]. So if v is a vertex of eccentricity d in a connected graph G, then [mathematical expression not reproducible].

Proposition 2. (a) Let G be a 5-connected triangulation of order n. Then

[mathematical expression not reproducible]

where [mathematical expression not reproducible] if n [equivalent to] 0 (mod 5), [mathematical expression not reproducible] if n [equivalent to] 1 (mod 5), [mathematical expression not reproducible] if n [equivalent to] 2 (mod 5), and [mathematical expression not reproducible] if n [equivalent to] 3,4 (mod 5).

(b) If G is a 3-connected quadrangulation of order n, then

[mathematical expression not reproducible]

where [mathematical expression not reproducible] if n [equivalent to] 0 (mod 3), [mathematical expression not reproducible] if n [equivalent to] 1 (mod 3), and [mathematical expression not reproducible] if n [equivalent to] 2 (mod 3).

Proof:

(a) It suffices to show that for an arbitrary vertex v of G we have

[mathematical expression not reproducible]

where [[epsilon]'.sub.n] = -10 if n = 0 (mod 5), [[epsilon]'.sub.n] = -14 if n = 1 (mod 5), [[epsilon]'.sub.n] = 0 if n = 2 (mod 5), and

[[epsilon]'.sub.n] = - 8 if n = 3,4 (mod 5).

Fix v [member of] V(G) and let d = e(v). Then

[mathematical expression not reproducible]

All ni are positive integers, [n.sub.0] = 1 and [mathematical expression not reproducible] [n.sub.i] = n. Since G is 5-connected we also have ni > 5 for all i [member of] {1,2,..., d - 1}. To bound F([n.sub.0], [n.sub.1],..., [n.sub.d]) from above we assume that n is fixed, and that d' [member of] N and [X.sub.max](n) = ([n.sub.0], [n'.sub.1],..., [n.sup.'.sub.d],) maximise the function F among all integers d and sequences X that satisfy these constraints. We first note that [mathematical expression not reproducible]. Indeed, if [n'.sub.i] > 5 for some i with 1 [less than or equal to] i [less than or equal to] d' - 1, then decreasing [n'.sub.i] by 1 and increasing [n'.sub.i+1] by 1 yields a new sequence X' that satisfies the above constraints and for which F(X') = F([X.sub.max](n)) + 1, contradicting the choice of [X.sub.max](n). Also, if [n'.sub.d], > 5, then decreasing [n'.sub.d], by 1, appending a new entry [n'.sub.d'+1] = 1 at the end and increasing d' by 1 yields a sequence that satisfies the requirement but whose F-value is greater, again a contradiction to the choice of [X.sub.max](n). Therefore, if q and r are positive integers with 1 [less than or equal to] r [less than or equal to] 5 such that n - 1 = 5q + r, then the unique sequence maximising F subject to the above constraints is

[X.sub.max](n) = (1, 5, 5,..., 5, r),

where the entry 5 appears exactly q times. If r [not equal to] 1, then it is easy to see that the unique sequence with the second largest F-value satisfying the constraints is the sequence

[X'.sub.max](n) = (1, 5, 5,..., 5, 6, r - 1),

where the entry 5 appears exactly q - 1 times.

CASE 1: n [equivalent to] 2 (mod 5).

Then F([n.sub.0], [n.sub.1],...,[n.sub.d]) [less than or equal to] F([X.sub.max](n)) = 1/10([n.sup.2] + 3n), as desired.

CASE 2: n [equivalent to] 0,1, 3,4 (mod 5).

Then ([n.sub.0], [n.sub.1],..., nd) = [X.sub.max](n) since otherwise, if ([n.sub.0], [n.sub.1],..., [n.sub.d]) = [X.sub.max](n), then [n.sub.d-1] = 5 and [n.sub.d] = r [not equal to] 1, contradicting Lemma 2(a). Therefore, F([n.sub.0], [n.sub.1],...,[n.sub.d]) < F([X'.sub.max](n)), and a simple calculation shows that F([X'.sub.max])(n) is the claimed upper bound on [sigma](v).

(b) The proof of (b) is analogous to that of (a), with only two differences: The condition [n.sub.i] [greater than or equal to] 5 for all i [member of] {1, 2,..., d - 1} in (a) is replaced by ni > 3 for all i [member of] {1, 2,..., d - 1}. Also, Lemma 2(b) implies that for n [equivalent to] 1, 2 (mod 3) we have ([n.sub.0], [n.sub.1],..., [n.sub.d]) [not equal to] [X.sub.max](n) and so F([n.sub.0], [n.sub.1],...,[n.sub.d]) [less than or equal to] F([X.sub.max](n)'), while for n = 0 (mod 3) Lemma 2(b) implies that ([n.sub.0], [n.sub.1],..., [n.sub.d]) [not equal to] [X.sub.max](n), [X.sub.max](n)' and thus F([n.sub.0], [n.sub.1],..., [n.sub.d]) < F([X.sub.max](n)'). []

4 Upper Bounds on the Wiener Index of Triangulations and Quad-rangulations

In this section we present asymptotically sharp upper bounds on the Wiener index of simple triangulations and simple quadrangulations, and improved bounds for simple 4-connected and 5-connected triangulations as well as simple 3-connected quadrangulations.

In the statements and proofs of our results we use the following notation. If S is a separating cycle of a plane graph G, then we denote the set of vertices inside S by A, and the set of vertices outside S by B. We often use S also for the set of vertices on this cycle, and we further let a := |A|, b := |B| and s := |S|. The following separator theorem by Miller is an important tool for the proof of our bounds.

Theorem 1. ([32]) If G is a 2-connected plane graph of order n whose faces have length at most l, then G has a separating cycle S of length at most [mathematical expression not reproducible], such that a,b [less than or equal to] 2/3 n.

We now define a plane graph which will be used in the proof of the main result of this section.

Definition 1. For p [member of] N with p > 3 let [F.sub.p] be the plane graph constructed as follows. Let C = [u.sub.0],[u.sub.1],..., [u.sub.p-1], [u.sub.0] be a cycle of length p. Inside C we add a cycle C' = [v.sub.0], [v.sub.1],..., [v.sub.2p-1][v.sub.0] of length 2p and edges [mathematical expression not reproducible] for i = 0,1,...,p - 1, with indices taken modulo p for the ui and modulo 2p for the vi. Inside C' we add a cycle C" = [w.sub.0], [w.sub.1],..., [w.sub.2p-1], [w.sub.0] of length 2p and edges [v.sub.i][w.sub.i], [v.sub.i][w.sub.i+1] for i = 0,1,..., 2p - 1, with all indices taken modulo 2p. Inside C" we add a new vertex z and join it to every vertex of C". The graph F4 is shown in Figure 4.

We define [F'.sub.p] to be a plane graph with the same vertex and edge set as [F.sub.p], but with the cycle C' outside the cycle C, the cycle C" outside the cycle C', and z lying in the unbounded face whose boundary is C".

Lemma 3. Let [F.sub.p] be the graph defined in Definition 1 above.

(a) [kappa]([F.sub.p]) [greater than or equal to] 5 for p > 3.

(b) If u [member of] V([F.sub.p]) and M [[subset].bar] V(C) with |M| [less than or equal to] 5, then [F.sub.p] contains a (u, M)-fan.

(c) If [M.sub.1], [M.sub.2] [[subset].bar] V(C) are two sets with |[M.sub.1]| = |[M.sub.2]| [less than or equal to] 5, then [F.sub.p] contains a set of |[M.sub.1]| disjoint paths from [M.sub.1] to [M.sub.2].

Proof: (a) It is easy to verify that any two vertices of [F.sub.p] are joined by five internally disjoint paths, hence [F.sub.p] is 5-connected.

(b) and (c) follow directly from [F.sub.p] being 5-connected. []

Theorem 2. Let [kappa] [member of] {3,4,5}. Then there exists a constant D such that

[mathematical expression not reproducible]

for every [kappa]-connected simple triangulation of order n.

Proof: Our proof is by induction on n. Define D := max{[D.sub.1],[D.sub.2]}, where [D.sub.1] is the smallest real x for which the inequality W(G) [mathematical expression not reproducible] holds for all [kappa]-connected simple triangulations G of order at most [10.sup.4], and [D.sub.2] is the smallest real x for which 8.1 + 0.76x [less than or equal to] x holds. We prove by induction on n that for all simple triangulations G of order n,

[mathematical expression not reproducible] (9)

Now (9) holds for all n [less than or equal to] [10.sup.4] by the choice of D. Let n > [10.sup.4]. By our induction hypothesis we may assume that (9) holds for all graphs of order less than n.

Since G is 2-connected, it follows by Theorem 1 that G contains a separating cycle S = [t.sub.0][t.sub.1]... [t.sub.s-1][t.sub.0] with a, b [less than or equal to] 2/3 n, where A, B, a, b, s are as in Theorem 1 and above it. Let H be the simple triangulation obtained from the plane graph G - A as follows. We first delete all edges between non-consecutive vertices of S that run inside the cycle S. Inside S we insert the graph [F.sub.s] by identifying the cycles S and C, specifically [t.sub.i] [member of] S with [u.sub.i] [member of] V([F.sub.s]) for i = 0,1,..., s - 1. Clearly, H is a simple triangulation of order b + 5s + 1. Similarly let K be the simple triangulation of order a + 5s + 1 obtained from the plane graph G - B by deleting all edges between non-consecutive vertices of S that run outside the cycle S and inserting [F.sub.s]' (a copy of [F.sub.s]) into the unbounded face, bounded by the vertices of S, by identifying ti[member of]S with [u.sub.i] [member of] V([F.sub.s]) for i = 0,1,..., s - 1.

For an illustration, see Figure 4. We claim that

H and K are [kappa]-connected. (10)

We prove (10) only for H, the proof for K is analogous. Let u, v be two arbitrary vertices of H. It suffices to show that there exist [kappa] internally disjoint (u, v)-paths in H. First assume that both, u and v, are in V([F.sub.s]), then it follows from Lemma 3(a) and [kappa] [less than or equal to] 5 that there are [kappa] internally disjoint (u, v)-paths in [F.sub.s], and thus in H. Now assume that exactly one of the two vertices, say u, is in V([F.sub.s]). Fix a vertex w[member of]AIt follows from the [kappa]-connectedness of G that in G there exist [kappa] internally disjoint (w, v)-paths [P.sub.1], [P.sub.2],..., [P.sub.[kappa]]. For i = 1, 2,..., [kappa] let [w.sub.i] be the last vertex of [P.sub.i] on C, and let [P'.sub.i] be the ([w.sub.i], v)-section of [P.sub.i]. By Lemma 3(b), [F.sub.s] contains a (u, {[w.sub.1],..., [w.sub.[kappa]]})-fan F. Then F together with [P.sub.1]',...,[P.sub.[kappa]]' yields a collection of [kappa] internally disjoint (u,v)-paths in H. Finally assume that both, u and v, are not in V([F.sub.s]). Then it follows from the [kappa]-connectedness of G that there exists internally disjoint (u, v)-paths [P.sub.1],[P.sub.2],...,[P.sub.[kappa]] in G. If none of these contains a vertex in V([F.sub.s]), then [P.sub.1],[P.sub.2],...,[P.sub.[kappa]] form a collection of [kappa] internally disjoint (u, v)-paths in H. If some of the paths, [P.sub.1],...,[P.sub.k] say, contain a vertex of V([F.sub.s]), then let ai and [a'.sub.i] be the first and last vertex, respectively, of [P.sub.i] in V([F.sub.s]). Let M = {[a.sub.1],...,[a.sub.k]} and M' = {[a'.sub.1],..., [a'.sub.k]}. By Lemma 3(c), [F.sub.s] contains k disjoint paths [Q.sub.1],...,[Q.sub.k] from M to M'. Then the (u, [a.sub.i])-sections and the ([a'.sub.i], v)-sections of the paths Pi together with [Q.sub.1],...,[Q.sub.k] and the paths [P.sub.k+1],..., [P.sub.[kappa]] form a collection of [kappa] internally disjoint (u, v)-paths in H. This proves (10).

The two graphs H and K have exactly the vertices in S in common. We now bound the Wiener index of G in terms of the Wiener indices of H and K, and the total distance of z in H and K.

[mathematical expression not reproducible] (11)

Indeed, for any two vertices x and y of G that are both in B [union] S, we have [d.sub.G](x, y) [less than or equal to] [d.sub.H] (x, y) + s/2 since a shortest (x, y)-path in H either contains only vertices in B [union] S, in which case it is also a path in G, or it contains vertices in V([F.sub.s])-S,in which case replacing the segment between the first and last occurrence of a vertex in V([F.sub.s])-S in the path by a segment of the cycle S that contains at most s/2 vertices yields an (x, y)-path in G. Similarly, if x and y are both in A [union] S, then [d.sub.G](x, y) [less than or equal to] [d.sub.K](x, y) + s/2. Finally, if x [member of] A and y [member of] B, then we can obtain an (x, y)-path in G from the concatenation of an (x, z)-path in K and a (z, y)-path in H by replacing z with a segment of S containing at most s/2 vertices. This proves (11).

We now bound each of the terms in (11). Since H and K are [kappa]-connected simple triangulations of order b + 5s + 1 and a + 5s + 1, respectively, we have by induction

[mathematical expression not reproducible] (12)

and

[mathematical expression not reproducible] (13)

It follows from the bounds on remoteness in Corollary 1(a),(b) and Proposition 2 that [mathematical expression not reproducible] for every vertex v of a [kappa]-connected triangulation of order n. Hence [sigma](z, H) [mathematical expression not reproducible] and [mathematical expression not reproducible]. Hence

[mathematical expression not reproducible]

and since a < a + 5s + 1 and b < b + 5s + 1,

[mathematical expression not reproducible] (14)

Hence we obtain from (11), (12), (13). and (14),

[mathematical expression not reproducible] (15)

We bound the terms of the right hand side of (15) separately. We make use of the facts that a + b + s = n, and that by Theorem 1 in conjunction with n > [10.sup.4] we have s [less than or equal to] [2.sup.3/2][n.sup.1/2] < 0.03n - 1. We bound the first term of (15) by (a + b + 10s + 2) (3) = (n + 9s + 2) (3) < (n + 9 * [2.sup.3/2][n.sup.1/2] + 2) (2). To bound the second term note that the real function f(x) = [x.sup.5/2] is concave up and that a, b [less than or equal to] 2/3 n by Theorem 1, which implies that [(a + 5s + 1).sup.5/2] + [(b + 5s + 1).sup.5/2] is maximised if a = 2/3]n and b = 1/3n - s (or vice versa). Therefore, [(a + 5s + 1).sup.5/2] + [(b + 5s + 1).sup.5/2] < [(2/3 n + 5s + 1).sup.5/2] + [(1n + 4s + 1).sup.5/2] < [(2/3 n + 0.15n).sup.5/2] + [(1/3 n + 0.12n).sup.5/2] = ([(2/3 + 0.15).sup.5/2] + [(1/3 + 0.12).sup.5/2])[n.sup.5/2] < 0.76[n.sup.5/2]. To bound the third term note that [kappa]-2/[kappa] < 1, a + 5s + 1 < n and b +5s + 1 < n, so [kappa]-2/[kappa](a + 5s + 1)(b + 5s + 1) < [n.sup.2]. To bound the fourth term note that [kappa]-3/2[kappa] < 1 and a + b < n, so [kappa]-3/2[kappa] (a + b) < n. Finally, (n/2) < 1/2 [n.sup.2], and so we bound the fifth term by (n/2) s/2 < [2.sup.-1/2][n.sup.5/2]. In total we obtain from (15),

[mathematical expression not reproducible]

Since n [greater than or equal to] [10.sup.4], we have 388/k + 8788/3K [n.sup.3/2] < 2[n.sup.5/2]. Also, 13/k + 0.76 D + 1 + [2.sup.-1/2] < 6.1 + 0.76 D, and so

[mathematical expression not reproducible]

since D satisfies 8.1 + 0.76 D[less than or equal to]D. The theorem follows. []

The following bound on the Wiener index of simple quadrangulations is proved in a similar way. The only difference is that a slightly modified version [Q.sub.p] of the plane graph [F.sub.p] is used in the proof. For an even p with p [greater than or equal to] 4 let [Q.sub.p] be the plane graph obtained from a cycle C = [u.sub.0], [u.sub.1],..., [u.sub.p-1], [u.sub.0] of length p, inside which we add a cycle C = [v.sub.0], [v.sub.1],..., [v.sub.p-1],[v.sub.0] of lengthp and edges [u.sub.i][v.sub.i] for i = 0,1,...,p - 1, inside which we add a vertex z and joint it to all [v.sub.i] with i even. It is easy to verify that a 3-connected quadrangualation with the insertion of [Q.sub.p] stays 3-connected. Apart from this difference, the proof of Theorem 3 follows closely that of Theorem 2, hence we omit the proof.

Theorem 3. Let [kappa] [member of] {2, 3}. Then there exists a constant C such that

[mathematical expression not reproducible]

for every [kappa]-connected simple quadrangulation G of order n. []

The leading coefficients in the bounds in Theorems 2 and 3 are optimal. This is shown by the graphs in Figures 5,6 and 7 for 3-connected triangulations, in Figures 8,9,10 and 11 for 4-connected triangulations, in Figures 12, 13, 15, 16 and 17 for 5-connected triangulations, in Figures 18 and 19 for 2-connected quadrangulations, and in Figures 20, 21 and 22 for 3-connected quadrangulations,

5 Computational Results and Conjectures

This section contains numerous figures and tables summarizing months of computer searches. None of this would have been possible without the help provided by Plantri, a program that generates triangulations and quadrangulation on numerous surfaces. For each category of problem (triangulations, 4-connected triangulations, 5-connected triangulations, quadrangulations and 3-connected quadrangulations) there is a table, which summarizes the largest Wiener index and remoteness found for a given order in that category, along with "Count", telling how many graphs attain the optimal value. Note that remoteness in this section is not normalized to keep the calculations in the domain of integers. In other words, in the Tables we show (n - 1)[rho](G) under the name of "Remoteness". Our Wiener index findings match those of [8] for triangulations. The number of isomorphism classes that our code searched matches the numbers in [5], [6], [7], [31], [36], verifying that the values that the search provides are in fact maximal. In each figure below, purple edges represent the repeating pattern and the black node marks a vertex which maximizes the remoteness. The computational evidence suggests that for sufficiently large order, the maximum Wiener index is uniquely realized in every category, while remoteness is not, except for quadrangulations.

5.1 Computational Results for Triangulations

Although the results of [22] made the Wiener index rows of Table 1 obsolete for n [greater than or equal to] 9, we still include it to show the multiplicity of maximizers up to n = 8 and the remoteness results.

5.2 Computational Results for 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] M. Aouchiche, P. Hansen, Proximity and remoteness in graphs: results and conjectures. Networks 58(no. 2) (2011), 95-102.

[3] Barefoot, C.A.; Entringer, R.C.; Szekely, L.A.; Extremal values for ratios of distances in trees. Discrete Appl. Math. 80 (1997), 37-56.

[4] R.A. Beezer, J.E. Riegsecker, B.Z. Smith, Using minimum degree to bound average distance. Discrete Math. 226 no. 1-3 (2001), 365-371.

[5] R. Bowen and S. Fisk, Generation of Triangulations of the Sphere. Math. Comp. 21 (1967), 250-252.

[6] 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.

[7] G. Brinkmann and B. McKay Construction of planar triangulations with minimum degree 5 Disc. Math. 301 (2005) 147-163.

[8] Z. Che, K.L. Collins, An upper bound on Wiener indices of maximal planar graphs. Discrete Appl. Math. (2019), Vol. 258, (2019) pp 76-86

[9] E. Czabarka, P. Dankelmann and L. Szekely, Maximum Wiener Index of Planar Triangulations and

Quadrangulations. AMS Spring Southeastern Sectional Meeting #1138 (2018), http://www.ams.org/meetings/sectional/2255_program.html

[10] E. Czabarka, P. Dankelmann, T. Olsen and L.A. Szekely, Wiener index and remoteness in triangulations and quadrangulations, arXiv:1905.06753 v.1. 16 May 2019

[11] P. Dankelmann, R.C. Entringer, Average distance, minimum degree and spanning trees. J. Graph Theory 33 no 1 (2000), 1-13.

[12] P. Dankelmann, S. Mukwembi, H.C. Swart, Average distance and edge-connectivity II. SIAM J. Discrete Math. 21 (2008), 1035-1052.

[13] P. Dankelmann, S. Mukwembi, H.C. Swart, Average distance and edge-connectivity I. SIAM J. Discrete Math. 22 (2008), 92-101.

[14] P. Dankelmann, S. Mukwembi, H.C. Swart, Average distance and vertex connectivity. J. Graph Theory 62 (2009), 157-177.

[15] P. Dankelmann, Proximity, remoteness, and minimum degree. Discrete Appl. Math. 184 (2015), 223-228.

[16] P. Dankelmann, New bounds on proximity and remoteness in graphs. Communications in Combinatorics and Optimization 1 no. 1 (2016), 28-40.

[17] K.Ch. Das, M.J. Nadjafi-Arani, On maximum Wiener index of trees and graphs with given radius. J. Combin. Optim. 34 (2017), 574-587.

[18] J..K. Doyle, J.E. Graver, Mean distance in a graph. Discrete Math. 7 (1977), 147-154.

[19] R.C. Entringer, D.E. Jackson, D.A. Snyder, Distance in graphs. Czech Math. J. 26 (1976), 283-296.

[20] M. Fischermann, A. Hoffmann, D. Rautenbach, L. Szekely and L. Volkmann. Wiener index versus maximum degree in trees. Discrete Appl. Math. 122 (1-3) (2002) 127-137.

[21] O. Favaron, M. Kouider, M. Maheo, Edge-vulnerability and mean distance. Networks 19 (1989), 493-504.

[22] D. Ghosh, E. Gyori, A. Paulos, N. Salia, O. Zamora, The maximum Wiener index of maximal planar graphs, arXiv:1912.02846, 5 December, 2019.

[23] I. Gutman, R. Cruz, J. Rada, Wiener index of Eulerian graphs. Discrete Appl. Math, 162 (2014), 247-250.

[24] F. Jelen, E. Triesch, Superdominance order and distance of trees with bounded maximum degree. Discrete Appl. Math. 125 (2-3) (2003), 225-233.

[25] S. Klavzar, M.J. Nadjafi-Arani, Wiener index in weighted graphs via unification of [theta]*-classes. European J. Combin. 36 (2014), 71-76.

[26] M. Knor, B. Luzar, R. Skrekovski, I. Gutman, On Wiener index of common neighborhood graphs. MATCH Commun. Math. Comput. Chem. 72 no. 1 (2014), 321-332.

[27] M. Knor, R. Skrekovski, A. Tepeh, Mathematical aspects of Wiener index. Ars Mathematica Contemporanea, 11 no. 2 (2016), 327-352.

[28] M. Kouider, P. Winkler, Mean distance and minimum degree. J. Graph Theory 25 no. 1 (1997): 95-99.

[29] X. Li, Y. Mao, I. Gutman, Inverse problem on the Steiner Wiener index. Discuss. Math. Graph Theory 38 no. 1 (2018), 83-95.

[30] L. Lovasz, Combinatorial Problems and Exercises. North Holland (1979).

[31] F. Lutz. Enumeration and random realization of triangulated surfaces. Discrete Diff. Geo. OWS 38 (2008) 235-253.

[32] G. I. Miller. Finding small cycle separators for 2-connected planar graphs. J. Comput. Sys. Sci. 32 no. 3 (1986), 265-279.

[33] S. Mukwembi, T. Vetrik, Wiener index of trees of given order and diameter at most 6. Bull. Austral. Math. Soc. 89 (2014), 379-396.

[34] J. Plesnik, On the sum of all distances in a graph or digraph. J. Graph Theory 8 (1984), 1-24.

[35] D.H. Rouvray, The rich legacy of half century of the Wiener index. In: Topology in Chemistry - Discrete Mathematics of Molecules, D.H. Rouvray and R.B. King (eds.), Horwood, Chichester (2002) 16-37.

[36] M. Scheucher, H. Schrezenmaier and R. Steiner, A note on universal point sets for planar graphs arXiv:1811.06482 [math.CO]

[37] N.J.A. Sloane, The On-Line Encyclopedia of Integer Sequences. https://oeis.org/

[38] S.G. Wagner, A class of trees and its Wiener index. Acta Appl. Math. 91 no. 2 (2006), 119-132.

[39] S.G. Wagner, H. Wang, G. Yu, Molecular graphs and the inverse Wiener index problem. Discrete Appl. Math. 157 no. 7 (2009), 1544-1554.

[40] H. Wang, G. Yu, All but 49 numbers are Wiener indices of trees. Acta Appl. Math. 91 no. 2 (2006), 15-20.

[41] H. Wiener, Structural determination of paraffin boiling points. J. Amer. Chem. Soc. 69 (1947), 17-20.

[42] B. Wu, W. Zhang, Average distance, radius and remoteness of a graph. Ars Math. Contemp. 7 (2014), 441-452.

[43] B. Zelinka, Medians and peripherians of trees. Arch. Math. (Brno) 4 (1968), 87-95.

Eva Czabarka (1,2) Peter Dankelmann (2*) Trevor Olsen (1) Laszlo A. Szekely (1,2[dagger])

(1) University of South Carolina, USA

(2) University of Johannesburg, South Africa

received 2020-05-13, revised 2020-10-29, accepted 2021-01-20.

(*) National Research Foundation of South Africa, grant number 118521

([dagger]) NSF DMS, grant number 1600811
Tab. 1: A summary of the largest Wiener Index and remoteness among all 
triangulations on n vertices, and a count for how many isomorphism 
classes attain this value.

Order  Wiener index  Count  Remoteness  Count

4      6             1      3           1
5      11            1      5           1
6      18            2      7           1
7      27            5      9           4
8      39            2      12          2
9      54            1      15          4
10     72            1      18          17
11     94            1      22          7
12     120           1      26          25
13     150           1      30          107
14     185           1      35          35
15     225           1      40          171
16     270           1      45          743
17     321           1      51          217
18     378           1      57          1199

Tab. 2: A summary of the largest Wiener Index and remoteness among all 
4-connected triangulations on n vertices, and a count for how many 
isomorphism classes attain this value.

Order  Wiener Index  Count  Remoteness  Count

6      18            1      6           1
7      27            1      8           1
8      38            2      10          2
9      51            4      12          4
10     68            1      15          4
11     87            1      18          6
12     110           1      21          16
13     135           1      24          50
14     166           1      28          24
15     199           1      32          66
16     238           1      36          186
17     279           1      40          653
18     328           1      45          250
19     379           1      50          879
20     438           1      55          2599
21     499           1      60          9429
22     570           1      66          3313

Tab. 3: A summary of the largest Wiener Index and remoteness among all 
5-connected triangulations on n vertices, and a count for how many 
isomorphism classes attain this value.

Order  Wiener index  Count  Remoteness  Count

12     108           1      18          1
13     --            0      --          0
14     159           1      23          1
15     189           1      26          1
16     222           2      29          1
17     259           1      34          1
18     300           1      37          1
19     342           1      41          2
20     391           1      45          4
21     444           1      49          9
22     500           2      55          4
23     560           1      59          11
24     630           1      64          36
25     702           1      69          66
26     780           1      74          193
27     867           1      81          39
28     955           1      86          240
29     1053          1      92          805
30     1156          1      98          1470
31     1265          1      104         4327
32     1384          1      112         763

Tab. 4: A summary of the largest Wiener Index and remoteness among all 
quadrangulations on n vertices, and a count for how many isomorphism 
classes attain this value.

Order  Wiener Index  Count  Remoteness  Count

4      8             1      4           1
5      14            1      6           1
6      23            1      9           1
7      34            2      12          1
8      50            1      16          1
9      68            1      20          1
10     93            1      25          1
11     120           1      30          1
12     156           1      36          1
13     194           1      42          1
14     243           1      49          1
15     294           1      56          1
16     358           1      64          1
17     424           1      72          1
18     505           1      81          1
19     588           1      90          1
20     688           1      100         1

Tab. 5: A summary of the largest Wiener Index and remoteness among all 
3-connected quadrangulations on n vertices, and a count for how many 
isomorphism classes attain this value.

Order  Wiener index  Count  Remoteness  Count

8      48            1      12          1
9      --            0      --          0
10     83            1      17          1
11     106           1      22          1
12     136           1      24          2
13     164           1      29          2
14     201           1      35          2
15     240           1      38          6
16     288           2      44          7
17     344           1      51          5
18     401           1      55          26
19     468           1      62          33
20     544           1      70          22
21     622           1      75          136
22     711           1      83          172
23     810           1      92          97
24     912           1      98          729
25     1026          1      107         923
26     1151          1      117         505
27     1280          1      124         3930
28     1422          1      134         4959
COPYRIGHT 2021 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2021 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Czabarka, Eva; Dankelmann, Peter; Olsen, Trevor; Szekely, Laszlo A.
Publication:Discrete Mathematics and Theoretical Computer Science
Article Type:Report
Geographic Code:1USA
Date:Jan 1, 2021
Words:8068
Previous Article:Anti-power j-fixes of the Thue-Morse word.
Next Article:Efficient Enumeration of Non-isomorphic Interval Graphs.
Topics:

Terms of use | Privacy policy | Copyright © 2022 Farlex, Inc. | Feedback | For webmasters |