Bulletin T.CXXXIII de l’Académie serbe des sciences et des arts − 2006 Classe des Sciences mathématiques et naturelles Sciences mathématiques, N\underline{o} 31

GRAPH CONNECTIVITY AND WIENER INDEX

I. GUTMAN, S. ZHANG

(Presented at the 8th Meeting, held on November 25, 2005)

A b s t r a c t. The graphs with a given number n of vertices and given (vertex or edge) connectivity k, having minimum Wiener index are determined. In both cases this is K_{k} + (K_{1} ∪ K_{n−k−1}) , the graph obtained by connecting all vertices of the complete graph K_{k} with all vertices of the graph whose two components are K_{n−k−1} and K_{1} .

AMS Mathematics Subject Classification (2000): 05C12, 05C40, 05C35 Key Words: graph connectivity, vertex–connectivity, edge–connectivity,

Wiener index; extremal graphs

1. Introduction

Let G be a connected graph whose vertex and edge sets are V (G) and E(G) , respectively. The distance between two vertices u and v, denoted by d_{G}(u, v) , is the length of a shortest path between u and v. The Wiener index of G, denoted by W (G) , is defined by

W (G) = ∑_{u,v∈V (G)} d_{G}(u, v) .

Details on the extensive (mathematical) research on the Wiener index can be found in the reviews [2, 3] and in the references cited therein. It should be noted that the Wiener index has significant applications in chemistry [5, 7].

Among connected graphs of order n, the path P_{n} has maximum Wiener index [4]. Therefore in the class of 1-connected and 1-edge–connected graphs of order n, P_{n} has the maximal W -value. Plesnik [6] showed that in the class of 2-connected and 2-edge–connected graphs of order n, the cycle C_{n} has maximal W -value. To the authors’ best knowledge, other relations between Wiener index and graph connectivity have not been established so far. Our aim is to contribute towards filling this gap, and to determine the minimum Wiener indices of graphs with prescribed number of vertices and connectivity, as well as to characterize the corresponding graphs.

Recall that if G is a connected graph on n vertices, different from the complete graph K_{n}, then the connectivity (or more precisely: the vertex– connectivity) of G is equal to k if all subgraphs of G, obtained by deleting from G fewer than k vertices are connected, and a subgraph obtained by deleting from G exactly k vertices is disconnected. One also says that G is k-connected. The vertex–connectivity–concept is not applicable to the complete graph. If k is the connectivity of G, then 1 ≤ k ≤ n − 2 .

Analogously, if G is a connected graph on n vertices, then the edge– connectivity of G is equal to k if all subgraphs of G, obtained by deleting from G fewer than k edges are connected, and a subgraph obtained by deleting from G exactly k edges is disconnected. If k is the edge–connectivity of G, then 1 ≤ k ≤ n − 1 , with k = n − 1 if and only if G = K_{n}.

Let G and H be two graphs with V (G) ∩ V (H) = ∅. By G ∪ H we denote the disjoint union of G and H. The join of G and H, denoted by G + H, is the graph with vertex set V (G + H) = V (G) ∪ V (H) and edge set E(G + H) = E(G) ∪ E(H) ∪ {uv|u ∈ V (G), v ∈ V (H)}.

For terminology and notations not defined here, we refer to the book [1].

2. Minimum Wiener Index of Graphs with Connectivity or Edge–connectivity k

Let G be a connected graph on n vertices. It is clear that the Wiener index is minimal if and only if G = K_{n}, in which case, W (G) = n(n − 1)/2 . In what follows we investigate when a graph with a given vertex– or edge– connectivity has minimum Wiener index.

Theorem 1. Let G be a k-connected, n-vertex graph, 1 ≤ k ≤ n − 2 . Then

W (G) ≥ \frac{1}{2} n(n + 1) − (k + 1) .

Equality holds if and only if G = K_{k} + (K_{1} ∪ K_{n−k−1}) .

P r o o f. Let G_{min} be the graph that among all graphs on n vertices and connectivity k has minimum Wiener index. Since the connectivity of G_{min} is k, there is a vertex–cut X ⊂ V (G_{min}) , such that |X| = k. Denote the components of G_{min} − X by G_{1}, G_{2}, …, G_{ω}. Then each of the subgraphs G_{1}, G_{2}, …, G_{ω} must be complete. Otherwise, if one of them would not be complete, then by adding an edge between two nonadjacent vertices in this subgraph we would arrive at a graph with the same number of vertices and same connectivity, but smaller Wiener index, a contradiction.

It must be ω = 2 . Otherwise, by adding an edge between a vertex from one component and a vertex from another component G_{1}, G_{2}, …, G_{ω}, if ω > 2 , then the resulting graph would still have connectivity k, but its Wiener index would decrease, a contradiction. So, G_{min} − X has two components G_{1} and G_{2} . By a similar argument, we conclude that any vertex in G_{1} and G_{2} is adjacent to any vertex in X.

Denote the number of vertices of G_{1} by n_{1} and that of G_{2} by n_{2} . Then n_{1} + n_{2} + k = n and by direct calculation we get

W (G_{min}) = \frac{1}{2} n_{1}(n_{1} − 1) + \frac{1}{2} n_{2}(n_{2} − 1) + \frac{1}{2} k(k − 1) + k(n_{1} + n_{2}) + 2 n_{1} n_{2}
= \frac{1}{2} n^{2} + (k − \frac{1}{2}) n + \frac{1}{2} k(k − 1) + n_{1} n_{2}

which for fixed n and k is minimum for n_{1} = 1 or n_{2} = 1 . This in turn means that G_{min} = K_{k} + (K_{1} ∪ K_{n−k−1}) . Direct calculation yields

W (G_{min}) = \frac{1}{2} n(n + 1) − (k + 1)

which completes the proof. □

The edge–connectivity version for Theorem 1 is also valid. Here the case k = n − 1 needs not be considered, since the only (n − 1)-edge–connected graph is K_{n}.

Theorem 2. Let G be a k-edge–connected, n-vertex graph, 1 ≤ k ≤ n − 2 . Then

W (G) ≥ \frac{1}{2} n(n − 1) + (n − k − 1) .

Equality holds if and only if G = K_{k} + (K_{1} ∪ K_{n−k−1}) .

P r o o f. Let now G_{min} denote the graph that among all graphs with n vertices and edge-connectivity k has minimum Wiener index. Let X be an edge–cut of G_{min} with |X| = k. Then G_{min} − X has two components, G_{1} and G_{2} . Both G_{1} and G_{2} must be complete graphs. Let |V (G_{1})| = n_{1} and |V (G_{2})| = n_{2} , n_{1} + n_{2} = n.

Denote the set of the end-vertices of the edges of X in G_{1} by S, and that in G_{2} by T . Let |V (G_{1} − S)| = a_{1} and |V (G_{2} − T)| = a_{2} .

There are

\frac{1}{2} n_{1}(n_{1} − 1) + \frac{1}{2} n_{2}(n_{2} − 1) + k = |E(G_{min})|

pairs of vertices at distance 1, and a_{1} a_{2} pairs of vertices at distance of 3. All other vertex pairs, namely

\binom{n}{2} − |E(G_{min})| − a_{1} a_{2}

are at distance 2. Consequently,

\begin{matrix}W (G_{min}) = & [\frac{1}{2} n_{1}(n_{1} − 1) + \frac{1}{2} n_{2}(n_{2} − 1) + k] \\ + & 2 [\binom{n}{2} − (\frac{1}{2} n_{1}(n_{1} − 1) + \frac{1}{2} n_{2}(n_{2} − 1) + k) − a_{1} a_{2}] + 3 [a_{1} a_{2}] \\ = & \frac{1}{2} n(n − 1) − k + n_{1} n_{2} + a_{1} a_{2} \end{matrix}

which for fixed n and k is minimum for n_{1} = 1 , a_{1} = 0 or n_{2} = 1 , a_{2} = 0 . This, as before, implies G_{min} = K_{k} + (K_{1} ∪ K_{n−k−1}) . □

3. Discussion

Theorems 1 and 2 establish that the graph with n vertices, connectivity k, and minimum Wiener index is same in the case of vertex– and edge– connectivity. One may wonder whether Theorem 1 implies Theorem 2, or vice versa. It appears (at least within the present considerations) that the proofs of these two theorems are independent.

As already mentioned, the 1– and 2-connected graphs with maximum Wiener indices are known. The natural question at this point is to ask for k-connected (k ≥ 2), n-vertex graphs having maximum W . This problem seems to be much more difficult, and, at this moment, we cannot offer any solution of it, not even for the case k = 3 .

Another related question is whether n-vertex, k-vertex–connected and n-vertex, k-edge–connected graphs with maximum W differ at all, and if yes, for which values of k and n.

Acknowledgement. Shenggui Zhang was supported by NSFC, SRF for ROCS of SEM, S & T Innovative Foundation for Young Teachers and DPOP in NPU, which he gratefully acknowledges.

REFERENCES

[1] J. A. B o n d y, U. S. R. M u r t y, Graph Theory with Applications, Macmillan, London and Elsevier, New York, 1976.

[2] A. A. D o b r y n i n, R. E n t r i n g e r, I. G u t m a n, Wiener index of trees: theory and applications, Acta Appl. Math. 66 (2001) 211–249.

[3] A. A. D o b r y n i n, I. G u t m a n, S. K l a v ž a r, P. Ž i g e r t, Wiener index of hexagonal systems, Acta Appl. Math. 72 (2002) 247–294.

[4] R. C. E n t r i n g e r, D. E. J a c k s o n, D. A. S n y d e r, Distance in graphs, Czech. Math. J. 26 (1976) 283–296.

[5] I. G u t m a n, Y. N. Y e h, S. L. L e e, Y. L. L u o, Some recent results in the theory of the Wiener number, Indian J. Chem. 32A (1993) 651–661.

[6] J. P l e s n i k, On the sum of all distances in a graph or digraph, J. Graph Theory 8 (1984) 1–21.

[7] D. H. R o u v r a y, The rich legacy of half century of the Wiener index, in: D. H. Rouvray, R. B. King (Eds.), Topology in Chemistry — Discrete Mathematics of Molecules, Horwood, Chichester, 2002, pp. 16–37.

Faculty of Science University of Kragujevac P. O. Box 60 34000 Kragujevac Serbia Department of Applied Mathematics Northwestern Polytechnical University Xi’an, Shaanxi 710072 P. R. China