# On the Maximal Eccentric Distance Sums of Graphs

Authors: Jianbin Zhang; Jianping Li
Journal: ISRN Applied Mathematics
 (2011)

---

## Abstract

IfG is a simple connected graph with vertex V(G), then the eccentric distance sum of G, denoted by ξd(G), is defined as ∑v∈V(G)ecG(v)DG(v), where ecG(v) is the eccentricity of the vertex v and DG(v) is the sum of all distances from the vertex v. Let n≥8. We determine the n-vertex trees with, respectively, the maximum, second-maximum, third-maximum, and fourth-maximum eccentric distance sums. We also characterize the extremal unicyclic graphs on n vertices with respectively, the maximal, second maximal, and third maximal eccentric distance sums.


---

## Body

## 1. Introduction

LetG be a simple connected graph with vertex set V(G) and edge set E(G). Let dG(u,v) be the distance (or length of a shortest path) between vertices u and v in G. For a vertex v∈V(G), the eccentricity ecG(v) is the maximum distance from v to any other vertex, and DG(v)=∑u∈V(G)dG(u,v) is the sum of all distances from v. The eccentric distance sum of G (EDS) is defined as (1.1)ξd(G)=∑v∈V(G)ecG(v)DG(v).This graph invariant was proposed by Gupta et al. in [1]. Like the Wiener index [2–4] and eccentric connectivity index [5–9], it turned to have high discriminating power and excellent predictability both with regard to biological and physical properties and to provide valuable leads for the development of safe and potent therapeutic agents of diverse nature. So, it is of interest to study the mathematical properties of this invariant.Yu et al. [10] considered the n-vertex trees and unicyclic graphs with minimal eccentric distance sums, respectively. Ilić et al. [11] proved that path Pn is the unique extremal trees with n vertices having maximum eccentric distance sum, and provided various lower and upper bounds for the eccentric distance sum. In this paper, we determine the n-vertex trees with, respectively, the maximum, second-maximum, third-maximum, and fourth-maximum eccentric distance sums for n≥8. We also characterize the extremal unicyclic graphs with the maximal, second maximal, and third maximal eccentric distance sums.


## 2. The Trees with Maximal Eccentric Distance Sums

Lemma 2.1.
Letu be a vertex of a connected graph G with at least two vertices. Let Gi be the graph obtained by identifying u and a vertex vi of a path Pn+1=v0v1⋯vn-1vn,  where 1≤i≤⌊n/2⌋.  Then, ξd(Gi-1)>ξd(Gi).Proof.
By the definition of EDS, we have(2.1)ξd(Gl)=∑v∈V(G)∖{u}ecGl(v)DGl(v)+∑j=0i-1[ecGl(vj)DGl(vj)+ecGl(vn-j)DGl(vn-j)]+∑k=in-iecGl(vk)DGl(vk).
Denoted by Al, Bl, and Cl respectively, the three sums of right equality above, we only need to prove the following three inequalities: Ai-1>Ai, Bi-1>Bi, Ci-1>Ci.
Note thatecGi-1(v)≥ecGi(v) for any v∈V(G), and
(2.2)DGi-1(v)-DGi(v)=[∑ω∈V(G)d(v,ω)+∑j=0i-1(d(u,v)+j)×2+∑j=in-i+1(d(u,v)+j)]-[∑ω∈V(G)d(v,ω)+∑j=0i(d(u,v)+j)×2+∑j=i+1n-i(d(u,v)+j)]=n-2i+1>0,
and thus, the inequality Ai-1>Ai holds.
Note that for anyi≤k≤n-i, ecGi-1(vk)≥ecGi(vk), DGi-1(vk)>DGi(vk), and thus Ci-1>Ci. So, it suffices to prove Bi-1>Bi.
LetecG(u)=s and n1=|V(G)|, and we distinguish the following two cases:
Case 1 (s≥n-i+1).
By direct calculation, it follows that(2.3)Bi-1=∑j=0i-1ecGi-1(vj)DGi-1(vj)+ecGi-1(vn-j)DGi-1(vn-j)=∑j=0i-1{[ecGi(vj)-1][∑v∈V(Pn+1)d(vj,v)+∑v∈V(G)∖{u}(dGi(vj,u)-1+dG(u,v))]+[ecGi(vn-j)+1][∑v∈V(Pn+1)d(vn-j,v)+∑v∈V(G)∖{u}(dGi(vn-j,u)+1+dG(u,v))]}=Bi+∑j=0i-1{∑v∈V(Pn+1)(n1-1)[ecGi(vn-j)-ecGi(vj)]+∑v∈V(Pn+1)[d(vn-j,v)-d(vj,v)]+(n1-1)[d(vn-j,u)-d(vj,u)]+2(n1-1)∑v∈V(Pn+1)[d(vn-j,v)-d(vj,v)]}.
For 0≤j≤i-1, it is easily seen that ecGi(vn-j)>ecGi(vj) and d(vn-j,u)≥d(vj,u). Furthermore, ∑v∈V(Pn+1)[d(vn-j,v)-d(vj,v)]=0, and thus, Bi-1>Bi.
Case 2 (s≤n-i).
For0≤j≤i-1, it is easily seen that ecGi-1(vj)=ecGi(vj), ecGi-1(vn-j)≥ecGi(vn-j). Then,
(2.4)Bi-1=∑j=0i-1[ecGi-1(vj)DGi-1(vj)+ecGi-1(vn-j)DGi-1(vn-j)]≥∑j=0i-1[ecGi(vj)DGi-1(vj)+ecGi(vn-j)DGi-1(vn-j)]=∑j=0i-1{ecGi(vj)[∑v∈V(Pn+1)d(vj,v)+∑v∈V(G)∖{u}(dGi(vj,u)-1+dG(u,v))]+ecGi(vn-j)[∑v∈V(Pn+1)d(vn-j,v)+∑v∈V(G)∖{u}(dGi(vn-j,u)+1+dG(u,v))]}=Bi+(n1-1)∑j=0i-1[ecGi(vn-j)-ecGi(vj)]>Bi,
where the last inequality follows as ecGi(vn-j)>ecGi(vj) for 0≤j≤i-1.By Lemma2.1 the inequality ξd(Gi)<ξd(G0) follows easily. Note that Gi has the number of pendent vertices greater than that of G0. Let T be a tree with at least i pendent vertices, where 3≤i≤n-1, by applying the above transformation to T repeatedly, then we can obtain a new tree with exactly i-1 pendent vertices, which has larger eccentric distance sum. So it is easy to prove the following result, which is also obtained by Ilić et al. in [11].Theorem 2.2.
Among all trees withn vertices, Pn has the maximal eccentric distance sum.LetTn,i be the tree obtained from Pn-1=v0v1⋯vn-2 by attaching a pendent vertex vn-1 to vi, where 1≤i≤⌊(n-2)/2⌋.Lemma 2.3.
Letn≥8. Then,
(2.5)ξd(Tn,1)-ξd(Tn,2)>2n-4,ξd(Tn,2)-ξd(Tn,3)>4n-10.Proof.
Suppose thatTn,i has the same vertex labeling as the above definition. We have two cases based on the parity of n. If n≥8 is even, then
(2.6)ξd(Tn,1)-ξd(Tn,2)=∑i=0n-1[ecTn,1(vi)DTn,1(vi)-ecTn,2(vi)DTn,2(vi)]=(n-2)⋅(-1)+(n-3)⋅(-1)+(n-4)⋅1+⋯+n2⋅1+(n2-1)⋅1+n2⋅1+⋯+(n-3)⋅1+(n-2)⋅1+12(3n2-19n+36)=14(9n2-62n+116)=2(n-2)(98n-448)+7>2(n-2),ξd(Tn,2)-ξd(Tn,3)=∑i=0n-1[ecTn,2(vi)DTn,2(vi)-ecTn,3(vi)DTn,3(vi)]=(n-2)⋅(-1)+(n-3)⋅(-1)+(n-4)⋅(-1)+(n-5)⋅1+⋯+n2⋅1+(n2-1)⋅1+n2⋅1+⋯+(n-3)⋅1+(n-2)⋅1+12(3n2-27n+72)=14(9n2-86n+220)=(4n-10)(916n-12732)+22716>4n-10.
Ifn≥9 is odd, then we make a similar calculation as above and obtain that
(2.7)ξd(Tn,1)-ξd(Tn,2)=2(n-2)(98n-448)+294>2(n-2),ξd(Tn,2)-ξd(Tn,3)=(4n-10)(916n-14332)+14916>4n-10.
These complete the proof.Lemma 2.4.
Among all trees onn vertices, where n≥8, Tn,3 has the maximal eccentric distance sum except Pn, Tn,1, and Tn,2.Proof.
suppose thatT is an n-vertex tree different from Pn, Tn,1, and Tn,2. Let p be the number of pendent vertices of T, then p≥3.
Ifp=3, then T is is a tree obtained by identifying three pendent vertices of three paths. Denote by r,s, and t, respectively, the lengths of the three paths, where r≥s≥t≥1 and r+s+t+1=n. Here, we denote it by Tn(r,s,t). Clearly, Tn(n-i-2,i,1)≅Tn,i(1≤i≤⌊(n-2)/2⌋). Suppose first that t=1. Then, T=Tn,i with i≥3. For 3≤i≤⌊(n-4)/2⌋, by Lemma 2.1, we have ξd(Tn,i+1)<ξd(Tn,i), and thus, ξd(T)≤ξd(Tn,3) with equality if and only if T≅Tn,3. Now suppose that t≥2, then r≥3 for n≥8, and by Lemma 2.1, we can obtain a new tree Tn(r,s+t-1,1) or Tn(s+t-1,r,1), which is not isomorphic to Tn,1, Tn,2, and Tn,3 and has larger eccentric distance sum.
Ifp≥5 by applying transformation of Lemma 2.1 to T repeatedly, we can obtain a new tree with exactly four pendant vertices and larger eccentric distance sum. Thus, it suffices to consider the case p=4.
Now, suppose thatp=4. In this case, T has at most two vertices with degree more than 2.
Case 1.
IfT has exactly two vertices with degree more than 2, say u and v, then d(u)=d(v)=3. Suppose that the length of path connecting u and v is a, the lengths of pendent paths at u are b,c, and the lengths of pendent paths at v are d, f. We denote this tree by Tn(a;b,c;d,f), where a≥1, b≥c, d≥f and a+b+c+d+f+1=n. If b≥3, then b,d+f+a≥3, and by Lemma 2.1 and above proof, we have ξd(Tn(a;b,c;d,f))<ξd(Tn(b,d+f+a,c))<ξd(Tn,3), where we suppose that b≥d+f+a≥c. If b=c=2, then by Lemma 2.1 and the result above we have ξd(Tn(a;2,2;d,f))<ξd(Tn(a;3,1;d,f))<ξd(Tn,3). If b=2, c=1 or b=1, c=1. Applying similar proof of Lemma 2.3, it is easily proven that ξd(Tn(n-6;1,1;2,1))-ξd(Tn(n-7;2,1;2,1))>0, ξd(Tn(n-5;1,1;1,1))-ξd(Tn(n-6;1,1;2,1))>0, and thus, we only need to prove that ξd(Tn(n-5;1,1;1,1))<ξd(Tn,3).
Here, we writeTn instead of Tn(n-5;1,1;1,1). Then, Tn is a tree obtained from the path v0v1⋯vn-4vn-3 by joining an isolated vertex vn-2 to vn-4 and an isolated vertex vn-1 to v1. Let Tn,1 be a tree obtained from Tn by deleting the edge v1vn-1 and adding the edge v0vn-1. If n≥8 is odd, then
(2.8)ecTn,1(v0)DTn,1(v0)-ecTn(v0)DTn(v0)=-(n-3),ecTn,1(v1)DTn,1(v1)-ecTn(v1)DTn(v1)=n-4,ecTn,1(vn-1)DTn,1(vn-1)-ecTn(vn-1)DTn(vn-1)=(n-2)(DTn(vn-1)+n-3)-(n-3)DTn(vn-1)=3n2-13n+162,ecTn,1(vn-3)DTn,1(vn-3)-ecTn(vn-3)DTn(vn-3)=ecTn,1(vn-2)DTn,1(vn-2)-ecTn(vn-2)DTn(vn-2)=(n-2)(DTn(vn-2)+1)-(n-3)DTn(vn-2)=n2-n2,ecTn,1(v(n-3)/2)DTn,1(v(n-3)/2)-ecTn(v(n-3)/2)DTn(v(n-3)/2)=(n-32+1)(DTn(v(n-3)/2)+1)-n-32DTn(v(n-3)/2)=n2+2n-114,
for 2≤i≤(n-5)/2, ecTn,1(vi)DTn,1(vi)-ecTn(vi)DTn(vi)=n-3-i; for (n-1)/2≤i≤n-4,
(2.9)ecTn,1(vi)DTn,1(vi)-ecTn(vi)DTn(vi)=(i+1)(DTn(vi)+1)-iDTn(vi)=i2-(n-4)i+n2-3n+22.
It follows that(2.10)ξd(Tn,1)-ξd(Tn(n-5;1,1;1,1))=5n2-15n+142+∑i=2(n-5)/2(n-3-i)+n2+2n-114+∑i=(n-1)/2n-4[i2-(n-4)i+n2-3n+22]=25n2-48n+1118+(n-5)(n+3)(2n-5)12=4n3+57n2-304n+33724>18n2-148n+3374=ξd(Tn,1)-ξd(Tn,3).
Thus,  ξd(Tn,3)>ξd(Tn(n-5;1,1;1,1)).
Similarly, for evenn, we have
(2.11)ξd(Tn,1)-ξd(Tn(n-5;1,1;1,1))=5n2-15n+142+∑i=2n/2-2(n-3-i)+∑i=n/2-1n-4[i2-(n-4)i+n2-3n+22]>18n2-148n+2564=ξd(Tn,1)-ξd(Tn,3),
and the inequality ξd(Tn,3)>ξd(Tn(n-5;1,1;1,1)) also holds.
Case 2.
IfT has an unique vertex of degree greater than 2, say w, then d(w)=4, and T is a tree obtained by identifying four pendent vertices of four paths. Denote by Tn(r,s,t,l) this tree, where r,s,t,l are the lengths of the four pendent paths respectively and r≥s≥t≥l≥1, r+s+t+l+1=n. If t=2, by Lemma 2.1, we have ξd(Tn(r,s,t,l))<ξd(Tn(r+1,s+1,l))<ξd(Tn,3). Similarly, we can show the result for t=l=1 and r≥2. In the following, we will prove that ξd(Tn(n-4,1,1,1))<ξd(Tn,3). We label the vertices of Tn(n-4,1,1,1) and Tn,3 such that Tn(n-4,1,1,1) can be viewed as obtained from the path v0v1⋯vn-4 by joining three isolated vertices vn-3, vn-2 and vn-1 to vn-4, and Tn,3 can be viewed as obtained from the path v0v1⋯vn-2 by joining an isolated vertex vn-1 to vn-5. Clearly, ecTn,3(vi)≥ecTn(n-4,1,1,1)(vi) for 0≤i≤n-3, DTn,3(vi)=DTn(n-4,1,1,1)(vi) for 0≤i≤n-5 and i=n-3, and DTn,3(vn-4)=DTn(n-4,1,1,1)(vn-4)+2. Note that
(2.12)ecTn,3(vn-2)DTn,3(vn-2)-ecTn(n-4,1,1,1)(vn-2)DTn(n-4,1,1,1)(vn-2)=(n-2)[DTn(n-4,1,1,1)(vn-2)+n-2]-(n-3)DTn(n-4,1,1,1)(vn-2)=(n-2)(n-2)+12(n-2)(n-3)+4=3n2-13n+222,ecTn,3(vn-1)DTn,3(vn-1)-ecTn(n-4,1,1,1)(vn-1)DTn(n-4,1,1,1)(vn-1)=(n-4)[DTn(n-4,1,1,1)(vn-2)-n+8]-(n-3)DTn(n-4,1,1,1)(vn-2)=-(n-2)(n-8)-12(n-2)(n-3)-4=-3n2-25n+462,
then
(2.13)ξd(Tn,3)-ξd(Tn(n-4,1,1,1))>3n2-13n+222-3n2-25n+462>0,
and this completes the proof.From Lemmas2.1 and 2.4, We have the followingTheorem 2.5.
Ifn≥8, then Tn,1, Tn,2, and Tn,3 are the unique trees with the second-maximal, third-maximal, and fourth-maximal eccentric distance sums among the trees on n vertices.


## 3. The Unicyclic Graphs with Maximal Eccentric Distance Sums

LetUn be the graph obtained from a path Pn-1=v0v1⋯vn-3vn-2 by joining the vertex vn-1 to vn-3 and vn-2. Let Qn be the graph obtained from a path Pn-1=v0v1⋯vn-3vn-2 by joining the vertex vn-1 to vn-4 and vn-2, and Bn be obtained by joining vn-1 to vn-4 and vn-3.Theorem 3.1.
LetG be a graph with n vertices and n edges; that is, G is an unicyclic graph, where n≥8. Then, ξd(G)≤ξd(Un), with equality if and only if G≅Un.Proof.
IfG≇Cn and G≇Un, then we can always find an edge e of G such that G-e is a tree with at least three pendent vertices and G-e≇Tn,1, Pn. It follows from Lemma 2.3 that
(3.1)ξd(G)<ξd(G-e)≤ξd(Tn,2)<ξd(Tn,1)-2(n-2)=ξd(Un).
Suppose thatG≅Cn and v is any vertex of Cn. If n≥8 is even, then
(3.2)ec(v)D(v)=n2[(1+2+⋯+n2-1)×2+n2]=n38.
By the definition of EDS, we have
(3.3)ξd(Un)=(ec(v0)D(v0)+ec(vn/2-1)D(vn/2-1))+(ec(vn/2-2)D(vn/2-2)+ec(vn/2)D(vn/2))+∑i≠0,n/2-1,n/2-2,n/2ec(vi)D(vi).
It is easily checked that
(3.4)ec(v0)D(v0)+ec(vn/2-1)D(vn/2-1)>n34,ec(vn/2-2)D(vn/2-2)+ec(vn/2)D(vn/2)=n34,
and for i≠0, n/2-1, n/2-2, n/2, ec(vi)≥n/2+1, D(vi)>n2/4. Then,
(3.5)ξd(Un)>n34+n34+(n-4)(n2+1)n24=n48+38n2(n-2)>n48=ξd(Cn).
We can prove the result for odd number n similarly, and thus complete the proof.Theorem 3.2.
Letn≥8. Then, Bn, Qn are the graph with, respectively, the second-maximal and third-maximal eccentric distance sums among all unicyclic graphs on n vertices.Proof.
IfG has a spanning tree T such that T≇Pn,Tn,1,Tn,2, then
(3.6)ξd(G)<ξd(T)≤ξd(Tn,3)<ξd(Tn,2)-4n+10=ξd(Qn).
Now suppose that any spanning tree of G is one of {Pn,Tn,1,Tn,2}. Then, G must be isomorphic to Cn, Qn or Bn. It can be proven easily that ξd(Cn)<ξd(Qn) by similar proof of Theorem 3.1. And by directed computation, we obtain that ξd(Bn)=ξd(Qn)+1. Thus, the result follows.



---

*Source: 421456-2011-06-14.xml*