# Chain Hexagonal Cacti with the Extremal Eccentric Distance Sum

Authors: Hui Qu; Guihai Yu
Journal: The Scientific World Journal
 (2014)

---

## Abstract

Eccentric distance sum (EDS), which can predict biological and physical properties, is a topological index based on the eccentricity of a graph. In this paper we characterize the chain hexagonal cactus with the minimal and the maximal eccentric distance sum among all chain hexagonal cacti of lengthn, respectively. Moreover, we present exact formulas for EDS of two types
of hexagonal cacti.


---

## Body

## 1. Introduction

Topological index, which can be used to characterize some property of the molecule graph, is a numeric and invariant quantity of a structure graph under graph isomorphism. Recently a novel graph invariant for predicting biological and physical properties—eccentric distance sum—was introduced by Gupta eta al. [1]. It has a vast potential in structure activity/property relationships. The authors [1] have shown that some structure activity and quantitative structure-property studies using eccentric distance sum were better than the corresponding values obtained using the Wiener index.Throughout this paper we only consider simple connected graphs. LetG be a simple connected graph with the vertex set V(G). For vertices u,v∈V(G), thedistanced(u,v) is defined as the length of the shortest path between u and v in G; DG(v) (or D(v) for short) denotes the sum of distances from v. TheeccentricityεG(v) (or ε(v) for short) of a vertex v is the maximum distance from v to any other vertex in G. The eccentric distance sum (EDS) of G is defined as
(1)ξd(G)=∑v∈V(G)‍εG(v)DG(v).In [2] authors investigated the eccentric distance sum of unicyclic graphs with given girth and characterize the extremal graphs with the minimal and the second minimal EDS; they also characterize the trees with the minimal EDS among the n-vertex trees of a given diameter. Iliç et al. [3] studied the various lower and upper bounds for the EDS in terms of other graph invariants including the Wiener index, the degree distance, the eccentric connectivity index, independence number, connectivity, matching number, chromatic number, and clique number. Zhang and Li [4] considered the maximal eccentric distance sum of graphs and determined the n-vertex trees with the first four maximal EDS. Also they characterized the n-vertex unicyclic graphs with the first three maximal EDS. Li et al. [5] investigated the trees with the minimal and second minimal EDS among n-vertex trees with given matching number; as a continuance they also determine the trees with the third and fourth minimal EDS among the n-vertex trees and characterized the trees with the second EDS among the n-vertex trees of a given diameter. For other recent results on EDS, the readers are referred to [6, 7].Acactus graph is a connected graph in which no edges lie in more than one cycle. Consequently, each block of a cactus graph is either an edge or a cycle. If all blocks of a cactus G are cycles of the same length m, the cactus is m-uniform. A hexagonal cactus is a 6-uniform cactus, that is, a cactus in which every block is a hexagon. A vertex shared by two or more hexagons is called acut vertex. If each hexagon of a hexagonal cactus G has at most two cut vertices and each cut vertex is shared by exactly two hexagons, we call G as achain hexagonal cactus. The number of hexagons in G is called thelength of the chain. Evidently, there exit exactly two hexagons which share only one cut vertex in any chain hexagonal cactus of length greater than one. Such hexagons are calledterminal hexagons, and other remaining hexagons are calledinternal hexagons. Let ℭn be the set of all chain hexagonal cacti of length n.Letu and v be two vertices in C6. They are said to be inorthoposition if they are adjacent in C6. If the distance between u and v is two, they are inmetaposition. They are inparaposition if the distance between them is three. An internal hexagon in a chain hexagonal cactus is calledorthohexagon,matahexagon, orparahexagon if its cut vertices are in ortho-, meta-, or paraposition, respectively. A chain hexagonal cactus of length n is called anorthochain if all its internal hexagons are orthohexagons, denoted by On. Themetachain andparachain of length n are defined in a completely analogous manner, denoted by Mn, Ln, respectively.Recently, Došlić and Måløy [8] considered the chain hexagonal cacti and derived explicit recurrences for their matching and independence polynomials and explicit recurrences for the number of matchings and independence set of certain types. The present paper was motivated by [8]; we investigate the eccentric distance sum of chain hexagonal cactus of length n and characterize the chain hexagonal cacti with the minimal and the maximal eccentric distance sums among all chain hexagonal cacti of length n(>2), respectively.


## 2. The Minimal and the Maximal EDS of Chain Hexagonal Cacti

In this section we determine the chain hexagonal cacti with the maximum and minimum EDS. In addition, we give exact formulas for EDS of two types of hexagonal cacti.Lemma 1.
LetLi be a parachain of lengths n0 (n0≥1) and u0∈V(Li) (see Figure 1). Let G0 be a chain hexagonal cactus of length n-n0 and vj∈V(G0)(j=0,1,2,3,4,5) (see Figure 1). Let G1 be the chain hexagonal cactus of length n obtained from Li and G0 by identifying u0 with v1. Let G2 be the graph obtained from Li and G0 by identifying u0 with v3. Let G3 be the graph obtained from Li and G0 by identifying u0 with v5. If n0≤⌊(n-1)/2⌋, then
(2)ξd(G1)<ξd(G2)<ξd(G3).Figure 1
Two chain hexagonal cactiLi and G0.Proof.
LetH0 be the hexagon consisting of vertices vi (i=0,1,…,5) in G0 (see Figure 1). By the definition of eccentric distance sum, we have
(3)ξd(Gi)=∑v∈V(Li-u0)‍εGi(v)DGi(v)+∑v∈V(H0)‍εGi(v)DGi(v)+∑v∈V(G0-H0)‍εGi(v)DGi(v),(i=1,2,3).
LetAi, Bi, and Ci (i=1,2,3) denote the three terms of right equality above, respectively. We only need to prove the following three inequalities:A3>A2>A1, B2+C2>B1+C1, and B3+C3>B2+C2.
For anyv∈V(Li-u0), we have(4)εG1(v)<εG2(v)<εG3(v),∑u∈V(Li-u0)‍dG1(u,v)=∑u∈V(Li-u0)‍dG2(u,v)=∑u∈V(Li-u0)‍dG3(u,v),∑u∈V(H0)‍dG1(u,v)=∑u∈V(H0)‍dG2(u,v)=∑u∈V(H0)‍dG3(u,v),∑u∈V(G0-H0)‍dG1(u,v)<∑u∈V(G0-H0)‍dG2(u,v)<∑u∈V(G0-H0)‍dG3(u,v),
which yield that A1<A2<A3.
For anyv∈V(G0), it is evident that εG1(v)≤εG2(v)≤εG3(v). Moreover,
(5)DGi(v)=∑u∈V(G0)‍dGi(u,v)+∑u∈V(Li-u0)‍dGi(u,v).
Note that ∑u∈V(G0)‍dG1(u,v)=∑u∈V(G0)‍dG2(u,v)=∑u∈V(G0)‍dG3(u,v). For the part ∑u∈V(Li-u0)‍dGi(u,v), we divide into two cases to deal with it.
Case
1
(
v
∈
V
(
G
0
-
H
0
)
). Consider the following:
(6)∑u∈V(Li-u0)‍dG2(u,v)=∑u∈V(Li-u0)‍(dG1(u,v)+1)=5n+∑u∈V(Li-u0)‍dG1(u,v),∑u∈V(Li-u0)‍dG3(u,v)=∑u∈V(Li-u0)‍(dG1(u,v)+2)=10n+∑u∈V(Li-u0)‍dG1(u,v).
Case
2 (v∈V(H0)={v0,v1,v2,v3,v4,v5}). Consider the following:
(7)∑u∈V(Li-u0)‍dG2(u,v0)=∑u∈V(Li-u0)‍(dG1(u,v0)+1)=5n+∑u∈V(Li-u0)‍dG1(u,v0),∑u∈V(Li-u0)‍dG3(u,v0)=∑u∈V(Li-u0)‍(dG1(u,v0)+2)=10n+∑u∈V(Li-u0)‍dG1(u,v0),∑u∈V(Li-u0)‍dG2(u,v1)=∑u∈V(Li-u0)‍(dG1(u,v1)+1)=5n+∑u∈V(Li-u0)‍dG1(u,v1),∑u∈V(Li-u0)‍dG3(u,v1)=∑u∈V(Li-u0)‍(dG1(u,v1)+2)=10n+∑u∈V(Li-u0)‍dG1(u,v1),∑u∈V(Li-u0)‍dG2(u,v2)=∑u∈V(Li-u0)‍(dG1(u,v2)+1)=5n+∑u∈V(Li-u0)‍dG1(u,v2),∑u∈V(Li-u0)‍dG3(u,v2)=∑u∈V(Li-u0)‍dG1(u,v2),∑u∈V(Li-u0)‍dG2(u,v3)=∑u∈V(Li-u0)‍(dG1(u,v3)-1)=-5n+∑u∈V(Li-u0)‍dG1(u,v3),∑u∈V(Li-u0)‍dG3(u,v3)=∑u∈V(Li-u0)‍dG1(u,v3),∑u∈V(Li-u0)‍dG2(u,v4)=∑u∈V(Li-u0)‍(dG1(u,v4)-1)=-5n+∑u∈V(Li-u0)‍dG1(u,v4),∑u∈V(Li-u0)‍dG3(u,v4)=∑u∈V(Li-u0)‍(dG1(u,v4)-2)=-10n+∑u∈V(Li-u0)‍dG1(u,v4),∑u∈V(Li-u0)‍dG2(u,v5)=∑u∈V(Li-u0)‍(dG1(u,v5)-1)=-5n+∑u∈V(Li-u0)‍dG1(u,v5),∑u∈V(Li-u0)‍dG3(u,v5)=∑u∈V(Li-u0)‍(dG1(u,v5)-2)=-10n+∑u∈V(Li-u0)‍dG1(u,v5).
Therefore, we have(8)C2-C1=∑v∈V(G0-H0)‍εG2(v)DG2(v)-∑v∈V(G0-H0)‍εG1(v)DG1(v)≥∑v∈V(G0-H0)‍εG2(v)[DG2(v)-DG1(v)]=∑v∈V(G0-H0)‍εG2(v)[∑u∈V(Li-u0)‍dG2(u,v)-∑u∈V(Li-u0)‍dG1(u,v)]≥∑v∈V(G0-H0)‍5n·εG1(v)≥25n(n-n0-1)·min⁡⁡{εG1(v)∣v∈V(G0-H0)}≥25n(n-n0-1)(n-n0+2).
Similarly, we have C3-C2≥25n(n-n0-1)(n-n0+2).
Forvi∈V(H0)(i=0,1,2,3,4,5), it follows that
(9)DG2(v0)=∑u∈V(G0)‍dG2(u,v0)+∑V(Li-u0)‍dG2(u,v0)DG2(v0)=∑u∈V(G0)‍dG1(u,v0)+∑V(Li-u0)‍dG1(u,v0)+5nDG2(v0)=DG1(v0)+5n,DG2(v1)=DG1(v1)+5n,DG2(v2)=DG1(v2)+5n,DG2(v3)=DG1(v3)-5n,DG2(v4)=DG1(v4)-5n,DG2(v5)=DG1(v5)-5n.
So we have(10)B2=∑v∈V(H0)‍εG2(v)DG2(v)=εG2(v0)DG2(v0)+εG2(v1)DG2(v1)+εG2(v2)DG2(v2)+εG2(v3)DG2(v3)+εG2(v4)DG2(v4)+εG2(v5)DG2(v5)≥εG1(v0)(DG1(v0)+5n)+εG1(v1)(DG1(v1)+5n)+εG1(v2)(DG1(v2)+5n)+εG1(v3)(DG1(v3)-5n)+εG1(v4)(DG1(v4)-5n)+εG1(v5)(DG1(v5)-5n)=B1+5nεG1(v0)+5nεG1(v1)+5nεG1(v2)-5nεG1(v3)-5nεG1(v4)-5nεG1(v5)=B1+5n[εG1(v0)+(εG1(v0)+1)+(εG1(v0)+1)=B1+5nf-(εG1(v0)+2)-(εG1(v0)+2)=B1+5nf-(εG1(v0)+3)]=B1-25n.
Similarly, we can get(11)B3-B2≥εG1(v0)·(5n)+εG1(v1)·(5n)+εG1(v2)·(-5n)+εG1(v3)·(5n)+εG1(v4)·(-5n)+εG1(v5)·(-5n)=5n(εG1(v0)+εG1(v0)+1-εG1(v0)-1+εG1(v0)+2-εG1(v0)-2-εG1(v0)-3)=-15n.
So we have
(12)B2+C2-B1-C1≥25n(n-n0-1)(n-n0+2)-25n>0,B3+C3-B2-C2≥25n(n-n0-1)(n-n0+2)-15n>0.
We complete the proof.By Lemma1, we can get the following result.Theorem 2.
LetGn be a chain hexagonal cactus of length n. Then
(13)ξd(On)≤ξd(Gn)≤ξd(Ln).In the following, we will calculate the values ofξd(On) and ξd(Ln).Theorem 3.
Consider(14)ξd(Ln)={132n(1875n3+1640n2+956n-80n3)ifniseven,132(1875n4+1260n3+974n2-12n-65)ifnisodd,ξd(On)={196n(625n3+7300n2+19988n-8032n3)ifniseven,196(625n4+7300n3+20138n2-6532n-795)ifnisodd.For somev∈V(Hk), assume that d(v,vk)=y and d(v,vk+1)=z. Then we have
(15)D(v)=∑u∈V(H1)‍d(u,v)+⋯+∑u∈V(Hk)‍d(u,v)+⋯+∑u∈V(Hn)‍d(u,v)-∑j=2n‍d(vj,v)=∑u∈V(H1)‍(d(u,v2)+d(v2,v))+⋯+∑u∈V(Hj);j<k‍(d(u,vj+1)+d(vj+1,v))+⋯+∑u∈V(Hk)‍d(u,v)+⋯+∑u∈V(Hj);j>k‍(d(u,vj)+d(vj,v))+⋯+∑u∈V(Hn)‍(d(u,vn)+d(vn,v))-∑j=2n‍d(vj,v)=(9+∑u∈V(H1)‍d(v2,v))+⋯+(9+∑u∈V(Hj);j<k‍d(vj+1,v))+⋯+9+⋯+(9+∑u∈V(Hj);j>k‍d(vj,v))+⋯+(9+∑u∈V(Hn)‍d(vn,v))-∑j=2n‍d(vj,v)=9n+∑u∈V(H1)‍[y+3(k-2)]+⋯+∑u∈V(Hj);j<k‍[y+3(k-(j+1))]+⋯+∑u∈V(Hk-1)‍[y+3(k-k)]+∑u∈V(Hk+1)‍[z+0]+∑u∈V(Hk+2)‍[z+3(k+2-(k+1))]+⋯+∑u∈V(Hj);j>k‍[z+3(j-(k+1))]+⋯+∑u∈V(Hn)‍[z+3(n-(k+1))]-∑j=2n‍d(vj,v)=9n+5∑j=1k-1‍[y+3(k-(j+1))]+5∑j=k+1n‍[z+3(j-(k+1))].For some hexagonHi (i≤n) (see Figure 2) in Ln, the eccentricity of every vertex on Hi can be derived as follows:
(16)ε(vi)=3(n+1-i),ε(vi1)=3(n+1-i)-1,ε(vi2)=3(n+1-i)-1,ε(vi3)=3(n+1-i)-2,ε(vi4)=3(n+1-i)-2,ε(vi+1)=3(n-i).Figure 2
The parachainLn.Whenn is even, we have
(17)ξd(Ln)=∑i=1n‍(∑v∈Hi‍ε(v)D(v))-∑i=2n‍ε(vi)D(vi)=2∑i=1n/2‍(∑v∈Hi‍ε(v)D(v))-∑i=2n‍ε(vi)D(vi)=2∑i=1n/2‍{3(n+1-i)[9n+5∑j=1i-1‍[0+3(i-(j+1))]3(n+1-i)fffffffff+5∑j=i+1n‍[3+3(j-(i+1))]]ffffffff+2[∑j=i+1n‍[3(n+1-i)-1]fffffffffffff×[9n+5∑j=1i-1‍[1+3(i-(j+1))]ffffffffffffffff+5∑j=i+1n‍[2+3(j-(i+1))]]]ffffffff+2[∑j=1i-1‍[3(n+1-i)-2]fffffffffffff×[9n+5∑j=1i-1‍[2+3(i-(j+1))]fffffffffffffffff+5∑j=i+1n‍[1+3(j-(i+1))]]]ffffffff+3(n-i)[9n+5∑j=1i-1‍[3+3(i-(j+1))]f+3(n-i)ffffffff+5∑j=i+1n‍[0+3(j-(i+1))]]}-2∑i=2n/2‍3(n+1-i)[9n+5∑j=1i-1‍[0+3(i-(j+1))]-2∑i=2n/2‍3(n+1-i)ffff+5∑j=i+1n‍[3+3(j-(i+1))]]-3·n2[9n+5∑j=1n/2‍[0+3(n2+1-(j+1))]-3·n2fff+5∑j=(n/2)+2n‍[3+3(j-(n2+2))]]=132n(1875n3+1640n2+956n-80).Whenn is odd, we have
(18)ξd(Ln)=∑i=1n‍(∑v∈Hi‍ε(v)D(v))-∑i=2n‍ε(vi)D(vi)=2∑i=1(n-1)/2‍(∑v∈Hi‍ε(v)D(v))+∑v∈H(n+1)/2‍ε(v)D(v)-∑i=2n‍ε(vi)D(vi)=2∑i=1(n-1)/2‍{3(n+1-i)[9n+5∑j=1i-1‍[0+3(i-(j+1))]5∑j=1i-1‍[0+3(i-(j+1))]fff+5∑j=i+1n‍[3+3(j-(i+1))]]fffffffffff+2[3(n+1-i)-1]fffffffffff×[9n+5∑j=1i-1‍[1+3(i-(j+1))]ffffffffffffff+5∑j=i+1n‍[2+3(j-(i+1))]]fffffffffff+2[3(n+1-i)-2]fffffffffff×[9n+5∑j=1i-1‍[2+3(i-(j+1))]ffffffffffffff+5∑j=i+1n‍[1+3(j-(i+1))]]fffffffffff+3(n-i)fffffffffff×[9n+5∑j=1i-1‍[3+3(i-(j+1))]fffffffffffffff+5∑j=i+1n‍[0+3(j-(i+1))]]}+2·3·n+12[9n+5∑j=1(n-1)/2‍[0+3(n+12-(j+1))]+2·3·n+12fff+5∑j=(n+3)/2n‍[3+3(j-(n+12+1))]]+2·2·[3(n+12)-1]×[9n+5∑j=1(n-1)/2‍[1+3(n+12-(j+1))]+5∑j=(n+3)/2n‍[2+3(j-(n+12+1))]]-2∑i=2(n+1)/2‍3(n+1-i)[9n+5∑j=1i-1‍[0+3(i-(j+1))]i-2∑i=2(n+1)/2‍3(n+1-i)ff+5∑j=i+1n‍[3+3(j-(i+1))]]=132(1875n4+1260n3+974n2-12n-65).LetHk be a hexagon in On. For some v∈V(Hk), assume that d(v,vk)=y and d(v,vk+1)=z. Similar to the case in Ln, we have
(19)D(v)=∑i=1n‍∑u∈V(Hi)‍d(u,v)-∑j=2n‍d(vj,v)=9n+5∑j=1i-1‍[y+i-(j+1)]+5∑j=i+1n‍[z+j-(i+1)].
For some hexagon Hi(i<(n+1)/2) (see Figure 3), the eccentricities of every vertex on Hi can be derived as follows:
(20)ε(vi1)=4+n-i,ε(vi2)=5+n-i,ε(vi3)=4+n-i,ε(vi4)=3+n-i,ε(vi)=3+n-i,ε(vi+1)=2+n-i.
When n is even, then we have
(21)ξd(On)=∑i=1n‍(∑v∈Hi‍ε(v)D(v))-∑i=2n‍ε(vi)D(vi)=2∑i=1n/2‍(∑v∈Hi‍ε(v)D(v))-∑i=2n‍ε(vi)D(vi)=2∑i=1n/2{(4+n-i)[9n+5∑j=1i-1‍[1+i-(j+1)]‍fffff(4+n-i)ff+5∑j=i+1n‍[2+j-(i+1)]]ffffffff+(5+n-i)[9n+5∑j=1i-1‍[2+i-(j+1)]ffffffff+(5+n-i)f+5∑j=i+1n‍[3+j-(i+1)]]ffffffff+(4+n-i)[9n+5∑j=1i-1‍[3+i-(j+1)]ffffffff+(4+n-i)f+5∑j=i+1n‍[2+j-(i+1)]]ffffffff+(3+n-i)[9n+5∑j=1i-1‍[2+i-(j+1)]ffffffff+(3+n-i)f+5∑j=i+1n‍[1+j-(i+1)]]ffffffff+(3+n-i)[9n+5∑j=1i-1‍[0+i-(j+1)]ffffffff+(3+n-i)f+5∑j=i+1n‍[1+j-(i+1)]]ffffffff+(2+n-i)[9n+5∑j=1i-1‍[1+i-(j+1)]ffffffff+(2+n-i)f+5∑j=i+1n‍[0+j-(i+1)]]}-2∑i=2n/2‍(n+3-i)[9n+5∑j=1i-1‍[0+i-(j+1)]ff-2∑i=2n/2‍(n+3-i)f+5∑j=i+1n‍[1+j+(i+1)]]-[n+3-(n2+1)]×[9n+5∑j=1n/2‍[0+n2+1-(j+1)]ffiiif+5∑j=(n/2)+2n‍[1+j-(n2+2)]]=196n(625n3+7300n2+19988n-8032).Figure 3
The orthochainOn.Whenn is odd, then we have
(22)ξd(On)=∑i=1n‍(∑v∈Hi‍ε(v)D(v))-∑i=2n‍ε(vi)D(vi)=2∑i=1(n-1)/2‍(∑v∈Hi‍ε(v)D(v))+∑v∈H(n+1)/2‍ε(v)D(v)-∑i=2n‍ε(vi)D(vi)=2∑i=1(n-1)/2{(4+n-i)[9n+5∑j=1i-1‍[1+i-(j+1)]‍fffffffff(4+n-i)f+5∑j=i+1n‍[2+j-(i+1)]]ffffffffff+(5+n-i)[9n+5∑j=1i-1‍[2+i-(j+1)]ffffffffffff(4+n-i)f+5∑j=i+1n‍[3+j-(i+1)]]ffffffffff+(4+n-i)[9n+5∑j=1i-1‍[3+i-(j+1)]ffffffffff+(4+n-i)f+5∑j=i+1n‍[2+j-(i+1)]]ffffffffff+(3+n-i)[9n+5∑j=1i-1‍[2+i-(j+1)]fffffffff+(3+n-i)ff+5∑j=i+1n‍[1+j-(i+1)]]ffffffffff+(3+n-i)[9n+5∑j=1i-1‍[0+i-(j+1)]ffffffffff+(3+n-i)f+5∑j=i+1n‍[1+j-(i+1)]]ffffffffff+(2+n-i)[9n+5∑j=1i-1‍[1+i-(j+1)]fffffffff+(2+n-i)ff+5∑j=i+1n‍[0+j-(i+1)]]}+2·(4+n-n+12)×[9n+5∑j=1(n-1)/2‍[1+n+12-(j+1)]+5∑j=(n+3)/2n‍[2+j-(n+32)]]+2·(5+n-n+12)×[9n+5∑j=1(n-1)/2‍[2+n+12-(j+1)]+5∑j=(n+3)/2n‍[3+j-(n+32)]]+2·(3+n-n+12)×[9n+5∑j=1(n-1)/2‍[0+n+12-(j+1)]+5∑j=(n+3)/2n‍[1+j-(n+32)]]-2∑i=2(n+1)/2‍(n+3-i)×[9n+5∑j=1i-1‍[0+i-(j+1)]+5∑j=i+1n‍[1+j-(i+1)]]=196(625n4+7300n3+20138n2-6532n-795).



---

*Source: 897918-2014-03-10.xml*