# Wiener Index of Graphs with Radius Two

Authors: Yin Chen; Baoyindureng Wu; Xinhui An
Journal: ISRN Combinatorics
 (2013)

---

## Abstract

The Wiener index of a graph is the sum of the distances between all pairs of vertices. It has been one of main descriptors that correlate a chemical compound's molecular graph with experimentally gathered data regarding the compound's characteristics. We characterize graphs with the maximum Wiener index among all graphs of ordern. with radius two. In addition, we pose a conjecture concerning the minimum Wiener index of graphs with given radius. If this conjecture is true, it will be able to answer an open question by You and Liu (2011).


---

## Body

## 1. Introduction

LetG=(V,E) be a connected graph. For two vertices u,v∈V, the distance dG(u,v) between u and v in G is the length of the shortest path connecting u and v in G. The eccentricity ecc(v) of a vertex v in G is the largest distance from v to another vertex of G; that is, max{d(v,w)∣w∈V(G)}. The diameter of G is the maximum eccentricity in G, denoted by diam(G). Similarly, the radius of G is the minimum eccentricity in G, denoted by rad(G). The Wiener index or total  distance of G, denoted by W=W(G), is the sum of all distances between unordered pairs of distinct vertices of G. In other words,
(1)rad(G)=minv∈V{ecc(v)},diam(G)=maxv∈V{ecc(v)},W(G)=∑u,v∈V‍d(u,v).The average distanceμ(G) of G is defined as μ(G)=W(G)/(n2). A vertex v∈V(G) is called a center of G if ecc(v)=rad(G). It is well known that every tree has either exactly one center or two adjacent centers. For the results on Wiener index of trees, we refer to Dobrynin et al. [1], and for some more results on Wiener index of graphs, one can see [2–12].Plesník [13] addresses a problem on distance of graphs, which remains unresolved.Problem 1.
What is the maximum total or average distance among all graphs of ordern with diameter d?To see how hard to solve Problem1, one just consider the following conjecture, due to DeLaViña and Waller [14].Conjecture 1 (see [14]).
Let G be a graph with diameterd>2 and order 2d + 1. Then W(G)≤W(C2d+1), where C2d+1 denotes the cycle of length 2d+1.For any connected graphG, rad(G)≤diam(G)≤2rad(G). By considering the close relationship between the diameter and the radius of a graph, it is natural to consider the following problem.Problem 2.
What is the maximum total or average distance among all graphs of ordern with radius r?By Lemma3 in Section 2, Problem 2 is more tractable than Problem 1; the graph with maximum total distance among all graphs of order n with radius r must be a tree. But, Problem 2 still seems to be quite challenging. The main focus of this paper is to tackle Problem 2 when the case r=2. We will show that the graph with the maximum Wiener index among all connected graphs with radius two is a tree with somewhat fractal-like structure when the number of vertices of graphs goes to infinity. It provides some clues for the further investigation of Problem 2 for the case r≥3.The following problem remains open, see You and Liu [10].Problem 3.
What is the minimum total or average distance among all graphs of ordern with radius r?It is easy to see that the complete graphKn has the minimum Wiener index among all connected graphs of order n (and so among all graphs of order n with radius one). For the case of radius two, it is not hard to prove that the extremal graph Gn of Problem 3 should be the following: Gn≅Kn∖M, if n is even, where M is a perfect matching; Gn≅Kn∖(F∪{e}), if n is odd, where F is a maximum matching of Kn and e is an edge incident with the vertex of degree n-1 in Kn∖F.We denote byGn,r,s the graph obtained in the following way, where n and r are three positive integers with n≥2r, r≥3, and n-2r+1≥s≥1: let u,v,x, and y be four consecutive vertices on C2r; replace v with a clique Ks of order s, replace x with a clique of order n-2r+2-s, join each vertex of a clique to all vertices of the other clique, join u to the all vertices of the Ks, and join y to all vertices of Kn-2r+2-s. It is clear that Gn,r,s is a graph of order n with radius r, and W(Gn,r,s)=W(Gn,r,s′) for any s,s′∈{1,…,r-1}.Conjecture 2.
Letn and r be two positive integers with n≥2r and r≥3. For any graph G of order n with radius r, W(G)≥W(Gn,r,1), with equality if and only if G≅Gn,r,s for s∈{1,…,r-1}.


## 2. Definitions and Lemmas

Lemma 3.
For any connected graphG, there exists a spanning tree T of G, such that rad(T)=rad(G) and W(T)≥W(G).Proof.
Letu be a center of G and T be a BFS-tree of G rooted at u. The tree T is one, as we desired.The path numberp(G) of a graph G is defined to be the maximum cardinality of a subset of vertices that induces a path. Erdős et al. [15] showed that for any connected graph G, p(G)≥2rad(G)-1.Lemma 4.
For atreeG with radius r, 2rad(G)≤p(G)≤2rad(G)+1.Proof.
LetPuv be the longest path of G. Since G is a tree, p(G)=|V(P)|. It is clear that a center w of G must be sitting on Puv, min{dG(wu),dG(wv)}≥r-1 and max{dG(wu),dG(wv)}≥r. The result then follows.Lemma 5.
LetT be a tree of order n with the maximum Wiener index among all trees with radius two. If n=4, then T≅P4, and p(T)=5, otherwise.Proof.
Ifn=4, the result is trivial. So, let n≥5. By Lemma 4, 4≤p(T)≤5. By contradiction, suppose that p(T)=4, and let P=v1v2v3v4 be a path on four vertices in T. Every other vertex not on P must be adjacent to v2 or v3. Without loss of generality, let dT(v2)≤dT(v3), and let x be a pendent vertex adjacent to v3. Set T′=T-v2v3+v2x. It is easy to check that W(T′)>W(T), contradicting the choice of T.Lemma 6.
LetT be a tree. Then(1)
the center ofT is a vertex or two adjacent vertices,(2)
the center ofT is one vertex if and only if diam(T)=2rad(T).The above two lemmas assert that ifT is a tree of order n with the maximum Wiener index among all trees of order at least five with radius two, then T has the unique center. We denote by Tn,t(n1,…,nt) the tree of order n with radius two and unique center vc such that d(vc)=t, N(vc)={v1,…,vt}, and d(vi)=ni+1 for each i. In particular, S(n,t)=Tn,t(n1,…,nt), with |ni-nj|≤1 for any i,j.Lemma 7.
LetT=Tn,t(n1,…,nt) be the tree as described above. Then
(2)W(T)=(2n2-5n+3)-(n-2)t-∑i=1t‍ni2.Proof.
Letxi=|{(u,v)∣u,v∈V(T),d(u,v)=i}|. Hence W(T)=∑i=14‍ixi, where
(3)x1=n-1,x2=(n-t-1)+(t2)+∑i=1t‍(ni2),x3=∑i=1t‍(n-t-1-ni)=(t-1)∑i=1t‍ni,x4=∑i=1t‍ni(n-t-1-ni)2.
By simple calculation, W(T)=(2n2-5n+3)-(n-2)t-∑i=1t‍ni2.The treesS(n,t) and S(n,t+1) when n=1+t+t2 are illustrated in Figure 1. We will see that W(S(n,t))=W(S(n,t+1)) if n=1+t+t2 in the next corollary. Note that if n=1+t+t2, each vertex in S(n,t), not a pendent vertex, has t children. In this sense, S(n,t) has a fractal-like structure. Our main goal is to prove that if T is a tree of order n with the maximum Wiener index among all trees with radius two, then T≅S(n,t0), where t0 can be determined. It will be shown in Theorem 9. For smaller value of n, one can see that those extremal graphs with radius two in Figure 2, and there exists two extremal graphs when n=1+t+t2 for some t≥2; for instance, see the graphs for t=2 (n=7) and t=3 (n=13) in Figure 2.Figure 1
The treesS(n,t) and S(n,t+1) when n=1+t+t2.Figure 2
The maximum wiener index with given radius two.Corollary 8.
Letn and t be two positive integers such that n≥t+2 and 1+t+kt≤n<1+t+(k+1)t for some integer k≥0, and let p=n-1-t-kt. Then
(4)W(S(n,t))=(2t2-t)k2+[3t2+(4p-1)t-2p]k+(t2+3tp+2p2-2p),
and if k=t and p=0, then W(S(n,t))=W(S(n,t+1))=2t4+2t3.Proof.
By the notation of the previous lemma, InS(n,t), the number of ni′s equal to k+1 is p and the number of ni′s equal to k is t-p. So, by Lemma 7,
(5)W(S(n,t))=(2n2-5n+3)-(n-2)t-∑i=1t‍ni2=(2n-3)(n-1)-(n-2)t-(p(k+1)2+(t-p)k2)=(2t+2tk+2p-1)(t+tk+p)-(t+tk+p-1)t-(2pk+p+tk2)=(2t2-t)k2+(3t2+(4p-1)t-2p)k+(t2+3tp+2p2-2p).
If k=t and p=0, by the above formula,
(6)W(S(n,t))=(2t2-t)t2+(3t2-t)t+t2=2t4+2t3.
Moreover, since 1+t+t2=1+(t+1)+(t+1)(t-1) and
(7)W(S(n,t+1))=[2(t+1)2-(t+1)](t-1)2+[3(t+1)2-(t+1)](t-1)+(t+1)2=2t4+2t3;
this provesW(S(n,t))=W(S(n,t+1))=2t4+2t3.


## 3. Main Results

For a clear understanding of our main theorem as follows, we make a remark. Ifn=1+t0+t02 for some positive integer t0, then t0=(4n-3-1)/2. By Corollary 8, W(S(n,t0))=W(S(n,t0+1)).Theorem 9.
LetT be a tree with the maximum Wiener index among all trees of order n with radius two. If n=1+t0+t02 for some positive integer t0, then T∈{S(n,(4n-3-1)/2),S(n,(4n-3+1)/2)}, and T≅S(n,t0) otherwise, where t0=min{i∣n-1-i-i2<0}.Proof.
The result is trivial forn≤4, and assume that n≥5. By Lemma 5, let vc be the unique center of T, and let d(vc)=t. Set N(vc)={v1,…,vt} and |N(vi)∖{vc}|=ni for 1≤i≤t. Lemma 7 implies that |ni-nj|≤1 for any i,j, and thus T≅S(n,t) for some t. To show t=t0, as specified in the theorem, it suffices to show that W(S(n,t))<W(S(n,t0)) for any t≠t0.
By Corollary8, W(S(n,t))=(2n2-5n+3)-(n-2)t-[q(k+1)2+(t-q)k2], where q=n-1-t-t⌊(n-t-1)/t⌋, 0≤q≤t-1, we have
(8)W(S(n,t))≤(2n2-5n+3)-(n-2)t-(n-t-1)2t.
Define a functionf(t)=(2n2-5n+3)-(n-2)t-(n-t-1)2/t, which is an upper bound of W(S(n,t)). Its derivative f′(t)=(n-1)2/t2-(n-1) has the unique root t=n-1. Observe that
(9)4n-3-12<n-1≤4n-3+12,
and since t0=min{i∣n-1-i-i2<0},
(10)4n-3-12<t0≤4n-3+12.
By the definition oft0, n=1+t0+t0k+p, where t0-2≤k≤t0 and 0≤p≤t0-1, and moreover, if k=t0, then p=0; if k=t0-2, then p>0.
Case  1 (t∈[2,t0-1]). Since
(11)f′(t)>0fort∈[2,t0-1],W(S(n,t))≤f(t)≤f(t0-1).
Moreover, sinceW(S(n,t0))=(2n2-5n+3)-(n-2)t0-(2pk+p+t0k2) and f(t0-1)=(2n2-5n+3)-(n-2)t0+(n-2)-(n-t0)2/(t0-1), we have
(12)(t0-1)(W(S(n,t0))-f(t0-1))=(n-t0)2-(2pk+p+t0k2)(t0-1)-(n-2)(t0-1)=(1+t0k+p)2-(2pk+p+t0k2)(t0-1)-(t0+t0k+p-1)(t0-1)=p2+(4+2k-2t0)p+(t0k2+3t0k+2t0-(k+1)t02)≥t0k2+3t0k+2t0-(k+1)t02=t0(k+1)(k+2-t0)≥0.
Thus,W(S(n,t0))≥f(t0-1), and together with (11), we have W(S(n,t0))≥W(S(n,t)) for any t∈[2,t0-1]. Observe from the above equation that W(S(n,t0))=W(S(n,t)) for some t∈[2,t0-1] if and only if k=t0-2,p=0. But, this contradicts the fact that if k=t0-2, then p=0. It follows that W(S(n,t0))>W(S(n,t)) for any t∈[2,t0-1].
Case  2 (t∈[t0+1,n-1)). Since f′(t)<0 for t∈[t0+1,n), W(S(n,t))≤f(t)≤f(t0+1). Since f(t0+1)=(2n2-5n+3)-(n-2)t0-(n-2)-(n-t0-2)2/(t0+1), we have
(13)(t0+1)[W(S(n,t0))-f(t0+1)]=(n-t0-2)2+(n-2)(t0+1)-(2pk+p+t0k2)(t0+1)=(t0k+p-1)2+(t0+t0k+p-1)(t0+1)-(2pk+p+t0k2)(t0+1)=p2-(2+2k)p+t0(k+1)(t0-k)=(p-k-1)2+(k+1)(t02-t0k-k-1).
Recall that t0-2≤k≤t0 and 0≤p≤t0-1. Since
(14)t02-t0k-k-1={t0+1,ifk=t0-2,0,ifk=t0-1,-t0-1,ifk=t0,
and the fact that if k=t0, then p=0, we have
(15)(t0+1)[W(S(n,t0))-f(t0+1)]=(p-k-1)2+(k+1)(t02-t0k-k-1)≥0,
with equality only if k=t0. It follows that W(S(n,t))≤f(t)≤f(t0+1)≤W(S(n,t0)), with W(S(n,t))=W(S(n,t0)) if and only if t=t0+1 and n=1+t0+t02. The proof is completed.



---

*Source: 906756-2013-03-03.xml*