# On Some Bounds and Exact Formulae for Connective Eccentric Indices of Graphs under Some Graph Operations

Authors: Nilanjan De; Anita Pal; Sk. Md. Abu Nayeem
Journal: International Journal of Combinatorics
 (2014)

---

## Abstract

The connective eccentric index of a graph is a topological index involving degrees and eccentricities of vertices of the graph. In this paper, we have studied the connective eccentric index for double graph and double cover. Also we give the connective eccentric index for some graph operations such as joins, symmetric difference, disjunction, and splice of graphs.


---

## Body

## 1. Introduction

LetG be a simple connected graph with vertex set V
(
G
) and edge set E
(
G
). Let n and m be the number of vertices and edges of G, respectively. We denote the degree of a vertex v of G by d
G
(
v
). For u
,
v
∈
V
(
G
), the distance between u and v in G is defined as the length of the shortest path between u and v in G and is denoted by d
G
(
u
,
v
). For a given vertex v of G, the eccentricity ε
G
(
v
) is the largest distance from v to any other vertices of G. The sum of eccentricities of all the vertices of G is denoted by θ
(
G
) [1]. If any vertex v
∈
V
(
G
) is adjacent to all the other vertices of G then v is called a well-connected vertex. Thus, if v
∈
V
(
G
) is a well-connected vertex, then ε
G
(
v
)
=
1. For example, all the vertices of a complete graph are well connected.Recently, a number of topological indices involving vertex degree and eccentricity were subject to a lot of mathematical as well as chemical studies. A topological index of this type, introduced by Gupta et al. [2], was named as the connective eccentric index and was defined as
(1)
C
ξ
(
G
)
=
∑
v
∈
V
(
G
)
‍
d
G
(
v
)
ε
G
(
v
)
.
Ghorbani [3] gave some bounds of connective eccentricity index and also computed this index for two infinite classes of dendrimers. De [4] reported some bounds for this index in terms of some graph invariants such as maximum and minimum degree, radius, diameter, first Zagreb index, and first Zagreb eccentricity index. In [5], Ghorbani and Malekjani computed the eccentric connectivity index and the connective eccentric index of an infinite family of fullerenes. In [6], Yu and Feng also derived some upper or lower bounds for the connective eccentric index and investigated the maximal and the minimal values of connective eccentricity index among all n-vertex graphs with fixed number of pendent vertices.In [3], Ghorbani showed that, for a vertex transitive graph G, the connective eccentric index is given by
(2)
C
ξ
G
=
∑
j
=
1
t
‍
A
j
d
G
x
i
ε
G
x
i
,
where A
1
,
A
2
,
…
,
A
t are the orbits of A
u
t
(
G
) under its natural action on V
(
G
) and x
i
∈
A
i, 1
≤
i
≤
t. In particular, if G is a regular graph, then C
ξ
(
G
)
=
n
δ
/
r
(
G
), where n is the number of vertices of G, which is a δ-regular graph, and r
(
G
) is the radius of G. Let K
n, C
n, Q
m, Π
m, A
m denote the complete graph with n vertices, the cycle on n vertices, m-dimensional hypercube, m-sided prism, and the m-sided antiprism, respectively. It can be easily verified that the explicit formulae for the connective eccentric index of K
n, C
n, Q
m, Π
m, A
m are as follows.Proposition 1.
Consider the following(3)
C
ξ
(
K
n
)
=
n
(
n
-
1
)
.Proposition 2.
Consider the following(4)
C
ξ
(
C
n
)
=
2
n
n
/
2
.Proposition 3.
Consider the following(5)
C
ξ
(
Q
m
)
=
2
m
.Proposition 4.
Consider the following(6)
C
ξ
(
Π
m
)
=
12
m
m
+
2
,
w
h
e
n
m
i
s
e
v
e
n
,
12
m
m
+
1
,
w
h
e
n
m
is
o
d
d
.Proposition 5.
Consider the following(7)
C
ξ
(
A
m
)
=
16
,
w
h
e
n
m
i
s
e
v
e
n
,
16
m
m
+
1
,
w
h
e
n
m
i
s
o
d
d
.Several studies on different topological indices related to graph operations of different kinds are available in the literature [7–11].In this paper, first we calculate connective eccentric index of double graph and double cover and hence the explicit formulae for the connective eccentric indices of join, symmetric difference, disjunction, and splice of graphs are obtained. For the definitions and different results on graph operations, such as join, symmetric difference, and disjunction, readers are referred to the book of Imrich and Klavžar [12].


## 2. Main Results

In this section, first we define and then compute eccentric connectivity index of double graph and double cover graph.


### 2.1. Connective Eccentric Index of Double Graph and Double Cover

Let us denote the double graph of a graphG by G
*, which is constructed from two copies of G in the following manner [13, 14]. Let the vertex set of G be V
(
G
)
=
v
1
,
v
2
,
…
,
v
n, and the vertices of G
* are given by the two sets X
=
x
1
,
x
2
,
…
,
x
n and Y
=
y
1
,
y
2
,
…
,
y
n. Thus, for each vertex v
i
∈
V
(
G
), there are two vertices x
i and y
i in V
(
G
*
). The double graph G
* includes the initial edge set of each copy of G, and, for any edge v
i
v
j
∈
E
(
G
), two more edges x
i
y
j and x
j
y
i are added. The graph P
3 and its double graph P
3
* is shown in Figure 1.Figure 1
The graphP
3 and its double graph P
3
*.Theorem 6.
The connective eccentric index of the double graphG
* is given by C
ξ
(
G
*
)
=
4
C
ξ
(
G
)
-
2
(
n
-
1
)
n
-
1
G, where n
-
1
G is the number of vertices with degree n
-
1, that is, of eccentricity one.Proof.
From the construction of double graph, it is clear thatd
G
*
(
x
i
)
=
d
G
*
(
y
i
)
=
2
d
G
(
v
i
), where v
i
∈
V
(
G
) and x
i
,
y
i
∈
V
(
G
*
) are the corresponding clone vertices of v
i. Also we can write ε
G
*
(
x
i
)
=
ε
G
*
(
y
i
)
=
ε
G
(
v
i
) when ε
G
(
v
i
)
≥
2 and ε
G
*
(
x
i
)
=
ε
G
*
(
y
i
)
=
ε
G
(
v
i
)
+
1 when ε
G
(
v
i
)
=
1.
Thus the connective eccentric index of double graphG
* is
(8)
C
ξ
G
*
=
∑
i
=
1
n
‍
d
G
*
x
i
ε
G
*
x
i
+
∑
i
=
1
n
‍
d
G
*
y
i
ε
G
*
y
i
=
2
∑
ε
G
(
v
i
)
≥
2
‍
2
d
G
v
i
ε
G
v
i
+
∑
ε
G
v
i
=
1
‍
2
d
G
v
i
ε
G
v
i
+
1
=
4
∑
ε
G
(
v
i
)
≥
2
‍
d
G
v
i
ε
G
v
i
+
∑
ε
G
v
i
=
1
‍
d
G
v
i
2
=
4
∑
ε
G
(
v
i
)
≥
2
‍
d
G
v
i
ε
G
v
i
+
∑
ε
G
(
v
i
)
=
1
‍
d
G
v
i
1
-
2
∑
ε
G
(
v
i
)
=
1
‍
d
G
v
i
=
4
C
ξ
(
G
)
-
2
(
n
-
1
)
n
-
1
G
.LetG
=
(
V
,
E
) be a simple connected graph with V
=
v
1
,
v
2
,
…
,
v
n. The extended double cover of G, denoted by G
*
*, is the bipartite graph with bipartition (
X
,
Y
) where X
=
x
1
,
x
2
,
…
,
x
n and Y
=
y
1
,
y
2
,
…
,
y
n in which x
i and y
j are adjacent if and only if either v
i and v
j are adjacent in G or i
=
j. For example, the extended double cover of the complete graph is the complete bipartite graph. This construction of the extended double cover was introduced by Alon [13] in 1986. Extended double cover of P
3 is illustrated in Figure 2.Figure 2
The graphP
3 and its extended double cover P
3
*
*.Theorem 7.
The connective eccentric index of the extended double coverG
*
* satisfies the inequality
(9)
C
ξ
G
*
*
<
2
C
ξ
G
-
n
n
-
1
G
-
2
.Proof.
IfG is a graph with n vertices and m edges, then, from definition, the extended double cover graph G
*
* consists of 2
n vertices and (
n
+
2
m
) edges and d
G
*
*
(
x
i
)
=
d
G
*
*
(
y
i
)
=
d
G
(
v
i
)
+
1 and ε
G
*
(
x
i
)
=
ε
G
*
(
y
i
)
=
ε
G
(
v
i
)
+
1 for i
=
1,2
,
…
,
n.
Thus the connective eccentric index of extended double cover graphG
*
* is given by
(10)
C
ξ
G
*
*
=
∑
i
=
1
n
‍
d
G
*
*
x
i
ε
G
*
*
x
i
+
∑
i
=
1
n
‍
d
G
*
y
i
ε
G
*
y
i
=
2
∑
ε
G
(
v
i
)
>
1
‍
d
G
v
i
+
1
ε
G
v
i
+
1
+
∑
ε
G
(
v
i
)
=
1
‍
d
G
v
i
+
1
2
<
2
∑
ε
G
(
v
i
)
>
1
‍
d
G
v
i
+
1
ε
G
v
i
+
∑
ε
G
(
v
i
)
=
1
‍
d
G
v
i
+
1
=
2
∑
ε
G
(
v
i
)
>
1
‍
d
G
v
i
ε
G
v
i
+
∑
ε
G
(
v
i
)
>
1
‍
1
ε
G
v
i
+
∑
ε
G
(
v
i
)
=
1
‍
d
G
v
i
+
∑
ε
G
(
v
i
)
=
1
‍
1
=
2
∑
ε
G
(
v
i
)
>
1
‍
d
G
v
i
ε
G
v
i
+
∑
ε
G
(
v
i
)
=
1
‍
d
G
v
i
+
2
∑
ε
G
(
v
i
)
>
1
‍
1
ε
G
v
i
-
∑
ε
G
(
v
i
)
=
1
‍
d
G
v
i
+
∑
ε
G
(
v
i
)
=
1
‍
1
=
2
C
ξ
G
+
2
n
-
n
-
1
G
-
n
-
1
n
-
1
G
+
n
-
1
G
=
2
C
ξ
(
G
)
-
n
n
-
1
G
-
2
.Now some exact formulae for the eccentric connectivity index of joins, symmetric difference, disjunction, and splice graphs are presented.


### 2.2. Join

The joinG
1
+
G
2 of two graphs G
1 and G
2, with disjoint vertex sets V
1, V
2 and edge sets E
1, E
2, is the graph union G
1
∪
G
2 together with all the edges joining V
1 and V
2; that is, G
1
+
G
2 consists of the vertex set V
1
∪
V
2 and edge set E
1
∪
E
2
∪
{
x
y
:
x
∈
V
1
,
y
∈
V
2
}.Theorem 8.
LetG
1 and G
2 be two graphs without well-connected vertices. Then, C
ξ
(
G
1
+
G
2
)
=
|
E
(
G
1
)
|
+
|
E
(
G
2
)
|
+
|
V
G
1
|
|
V
(
G
2
)
|.Proof.
Letn
1 and n
2 be the numbers of vertices in G
1 and G
2, respectively. Thus, |
V
(
G
1
+
G
2
)
|
=
|
V
1
|
+
|
V
2
|
=
n
1
+
n
2. For vertices u
∈
V
1 and v
∈
V
2, it holds that d
G
1
+
G
2
(
u
)
=
d
G
1
(
u
)
+
n
2 and d
G
1
+
G
2
(
v
)
=
d
G
2
(
v
)
+
n
1. Since none of G
1 and G
2 contains well-connected vertices, then, for every u
∈
V
(
G
1
+
G
2
), ε
G
1
+
G
2
(
u
)
=
2. So, from definition of connective eccentric index, we have
(11)
C
ξ
G
1
+
G
2
=
∑
v
∈
V
(
G
1
)
‍
d
G
1
+
G
2
v
ε
G
1
+
G
2
v
+
∑
v
∈
V
(
G
2
)
‍
d
G
1
+
G
2
v
ε
G
1
+
G
2
v
=
1
2
∑
v
∈
V
(
G
1
)
‍
d
G
1
(
v
)
+
n
2
+
∑
v
∈
V
(
G
2
)
‍
d
G
2
(
v
)
+
n
1
from where the desired result follows.Now we generalize the above result forn disjoint graphs G
1
,
G
2
,
…
,
G
n.Theorem 9.
LetG
1
,
G
2
,
…
,
G
n be n graphs with disjoint vertex sets V
i
=
V
(
G
i
) and edge sets E
i
=
E
(
G
i
), 1
≤
i
≤
n, without well-connected vertices. Then,
(12)
C
ξ
G
1
+
G
2
+
⋯
+
G
n
=
∑
i
=
1
n
‍
E
G
i
+
1
2
∑
i
=
1
n
‍
V
G
i
2
-
1
2
∑
i
=
1
n
‍
V
G
i
2
.Proof.
From definition of join, we haved
G
1
+
G
2
+
⋯
+
G
n
(
v
j
)
=
d
G
i
(
v
j
)
+
|
V
(
G
1
+
G
2
+
⋯
+
G
n
)
|
-
|
V
(
G
i
)
| and since none of G
1
,
G
2
,
…
,
G
n contains any well-connected vertex, we have ε
G
1
+
G
2
+
⋯
+
G
n
(
v
j
)
=
2 for all v
j
∈
V
(
G
i
).
Thus the connective eccentric index ofG
1
+
G
2
+
⋯
+
G
n is given by
(13)
C
ξ
G
1
+
G
2
+
⋯
+
G
n
=
∑
i
=
1
n
‍
∑
j
=
1
V
(
G
i
)
‍
d
G
1
+
G
2
+
⋯
+
G
n
v
j
ε
G
1
+
G
2
+
⋯
+
G
n
v
j
=
∑
i
=
1
n
‍
∑
j
=
1
V
(
G
i
)
‍
d
G
i
v
j
+
V
G
1
+
G
2
+
⋯
+
G
n
-
V
G
i
2
=
1
2
E
G
1
+
E
G
2
+
⋯
+
E
G
n
V
G
1
2
+
V
G
2
2
+
⋯
+
V
G
n
2
+
V
G
1
+
G
2
+
⋯
+
G
n
×
V
G
1
+
V
G
2
+
⋯
+
V
G
n
-
V
G
1
2
+
V
G
2
2
+
⋯
+
V
G
n
2
from where the desired result follows.The following corollaries are direct consequences of the theorem.Corollary 10.
Ifn
G denotes the join of n copies of G, then
(14)
C
ξ
(
n
G
)
=
n
E
G
+
n
(
n
-
1
)
2
V
G
2
.Corollary 11.
LetG
=
K
m
1
,
m
2
,
…
,
m
n be the complete n-partite graph [see Figure 3] having v
=
|
V
(
G
)
| number of vertices. Here the vertex set can be partitioned into n subsets V
1
,
V
2
,
…
,
V
n such that V
1
∪
V
2
∪
⋯
∪
V
n
=
V
(
G
) and V
i
∩
V
j
=
ϕ, i
≠
j, 1
≤
i, j
≤
n. From definition of join it is clear that G
=
K
m
1
,
m
2
,
…
,
m
n is the join of n empty graphs with m
1
,
m
2
,
…
,
m
n number of vertices. Then the connective eccentric index of G
=
K
m
1
,
m
2
,
…
,
m
n is given by
(15)
C
ξ
(
K
m
1
,
m
2
,
…
,
m
n
)
=
∑
1
≤
i
≤
n
1
≤
j
≤
n
i
≠
j
‍
m
i
m
j
.Figure 3
The completen-partite graph.


### 2.3. Symmetric Difference

LetG
1 and G
2 be two graphs with vertex sets V
(
G
1
) and V
(
G
2
) and edge sets E
(
G
1
) and E
(
G
2
). Then the symmetric difference of G
1 and G
2, denoted by G
1
⊕
G
2, is the graph with vertex set V
(
G
1
)
×
V
(
G
2
) in which any two vertices (
u
1
,
u
2
) are adjacent to (
v
1
,
v
2
) whenever u
1 is adjacent to v
1 in G
1 or u
2 is adjacent to v
2 in G
2, but not both. From definition of symmetric difference, the degree of a vertex (
u
1
,
u
2
) of G
1
⊕
G
2 is given by [12]
(16)
d
G
1
⊕
G
2
u
1
,
u
2
=
V
G
2
d
G
1
u
1
+
V
G
1
d
G
2
u
2
-
2
d
G
1
(
u
1
)
d
G
2
(
u
2
)
.Theorem 12.
The connective eccentric index of the symmetric differenceG
1
⊕
G
2 of two graphs G
1 and G
2 is given by
(17)
C
ξ
G
1
⊕
G
2
=
E
G
1
V
G
2
2
+
E
G
2
V
G
1
2
-
4
E
G
1
E
G
2
,
where none of G
1 and G
2 contains well-connected vertices.Proof.
Since the distance between any two vertices of a symmetric difference cannot exceed two, if none of the components contains well-connected vertices, the eccentricity of all vertices is constant and is equal to two; that is,ε
G
1
⊕
G
2
(
u
1
,
u
2
)
=
2, for all vertices (
u
1
,
u
2
) [7, 8].
Thus the connective eccentric index of symmetric differenceG
1
⊕
G
2 of two graphs G
1 and G
2 is given by
(18)
C
ξ
G
1
⊕
G
2
=
∑
(
u
1
,
u
2
)
∈
V
(
G
1
⊕
G
2
)
‍
d
G
1
⊕
G
2
u
1
,
u
2
ε
G
1
⊕
G
2
u
1
,
u
2
=
1
2
∑
u
1
∈
V
(
G
1
)
‍
∑
u
2
∈
V
(
G
2
)
‍
V
G
2
d
G
1
u
1
+
V
G
1
d
G
2
u
2
-
2
d
G
1
u
1
d
G
2
u
2
V
G
1
=
1
2
V
G
2
2
∑
u
1
∈
V
(
G
1
)
‍
d
G
1
(
u
1
)
+
V
G
1
2
∑
u
2
∈
V
(
G
2
)
‍
d
G
2
(
u
2
)
-
2
∑
u
1
∈
V
(
G
1
)
‍
d
G
1
(
u
1
)
∑
u
2
∈
V
(
G
2
)
‍
d
G
2
(
u
2
)
from where the desired result follows.


### 2.4. Disjunction

The disjunctionG
1
∨
G
2 of two graphs G
1 and G
2 is the graph with vertex set V
(
G
1
)
×
V
(
G
2
) in which (
u
1
,
u
2
) is adjacent to (
v
1
,
v
2
) whenever u
1 is adjacent to v
1 in G
1 or u
2 is adjacent to v
2 in G
2. Obviously, the degree of a vertex (
u
1
,
u
2
) of G
1
∨
G
2 is given by [7, 8]
(19)
d
G
1
∨
G
2
u
1
,
u
2
=
V
G
2
d
G
1
(
u
1
)
+
V
G
1
d
G
2
v
2
-
d
G
1
u
1
d
G
2
v
2
.Theorem 13.
The connective eccentric index of the disjunctionG
1
∨
G
2 of two graphs G
1 and G
2 is given by
(20)
C
ξ
G
1
∨
G
2
=
E
G
1
V
G
2
2
+
E
G
2
V
G
1
2
-
2
E
G
1
E
G
2
,
where none of G
1 and G
2 contains well-connected vertices.Proof.
Since the distance between any two vertices of a disjunction cannot exceed two, if none of the components contains well-connected vertices, the eccentricity of all vertices is constant and equal to two [7, 8]. Then the connective eccentric index of the disjunction G
1
∨
G
2 of two graphs G
1 and G
2 is computed as
(21)
C
ξ
G
1
∨
G
2
=
∑
(
u
i
,
v
j
)
∈
V
(
G
1
∨
G
2
)
‍
d
G
1
∨
G
2
u
1
,
u
2
ε
G
1
∨
G
2
u
1
,
u
2
=
1
2
∑
u
1
∈
V
(
G
1
)
‍
∑
v
2
∈
V
(
G
2
)
‍
V
G
2
d
G
1
u
1
+
V
G
1
d
G
2
u
2
-
d
G
1
(
u
1
)
d
G
2
(
u
2
)
from where the desired result follows.


### 2.5. Splice

LetG
1
=
(
V
1
,
E
1
) and G
2
=
(
V
2
,
E
2
) be two graphs V
1
∩
V
2
=
ϕ. Let v
1
∈
V
1 and v
2
∈
V
2 be two given vertices of G
1 and G
2, respectively. A splice of G
1 and G
2 at the vertices v
1 and v
2 is obtained by identifying the vertices v
1 and v
2 in the union of G
1 and G
2 and is denoted by S
(
G
1
,
G
2
,
v
1
,
v
2
) [15]. Different topological indices of the splice graphs have already been computed [16]. Let u
∈
V
(
S
); then ε
1
(
u
) denotes the eccentricity of u as a vertex of G
1
,
ε
2
(
u
) denotes the eccentricity of u as a vertex of G
2, and ɛ
(
u
) denotes the eccentricity of u as a vertex of S. Let d
S
(
x
) be the degree of the vertex x
∈
V
(
S
). Then the connective eccentric index of S
(
G
1
,
G
2
,
v
1
,
v
2
) is computed as follows.Theorem 14.
The connective eccentric index of splice ofG
1 and G
2 is given by
(22)
C
ξ
S
=
∑
x
∈
V
1
‍
d
S
x
max
⁡
d
G
1
x
,
v
1
+
ε
1
x
ε
2
v
2
+
∑
y
∈
V
2
‍
d
S
(
y
)
max
⁡
d
G
2
(
y
,
v
2
)
+
ε
1
(
v
1
)
ε
2
(
y
)
.Proof.
For any vertexx
∈
V
1, Sharafdini and Gutman [16] showed that
(23)
ɛ
(
x
)
=
max
⁡
d
G
1
(
x
,
v
1
)
+
ε
1
(
x
)
ε
2
(
v
2
)
.
Similarly, for any vertex y
∈
V
2,
(24)
ɛ
(
y
)
=
max
⁡
d
G
2
(
y
,
v
2
)
+
ε
1
(
v
1
)
ε
2
(
y
)
.
Thus, the desired result follows from the definition of connective eccentric index.


## 2.1. Connective Eccentric Index of Double Graph and Double Cover

Let us denote the double graph of a graphG by G
*, which is constructed from two copies of G in the following manner [13, 14]. Let the vertex set of G be V
(
G
)
=
v
1
,
v
2
,
…
,
v
n, and the vertices of G
* are given by the two sets X
=
x
1
,
x
2
,
…
,
x
n and Y
=
y
1
,
y
2
,
…
,
y
n. Thus, for each vertex v
i
∈
V
(
G
), there are two vertices x
i and y
i in V
(
G
*
). The double graph G
* includes the initial edge set of each copy of G, and, for any edge v
i
v
j
∈
E
(
G
), two more edges x
i
y
j and x
j
y
i are added. The graph P
3 and its double graph P
3
* is shown in Figure 1.Figure 1
The graphP
3 and its double graph P
3
*.Theorem 6.
The connective eccentric index of the double graphG
* is given by C
ξ
(
G
*
)
=
4
C
ξ
(
G
)
-
2
(
n
-
1
)
n
-
1
G, where n
-
1
G is the number of vertices with degree n
-
1, that is, of eccentricity one.Proof.
From the construction of double graph, it is clear thatd
G
*
(
x
i
)
=
d
G
*
(
y
i
)
=
2
d
G
(
v
i
), where v
i
∈
V
(
G
) and x
i
,
y
i
∈
V
(
G
*
) are the corresponding clone vertices of v
i. Also we can write ε
G
*
(
x
i
)
=
ε
G
*
(
y
i
)
=
ε
G
(
v
i
) when ε
G
(
v
i
)
≥
2 and ε
G
*
(
x
i
)
=
ε
G
*
(
y
i
)
=
ε
G
(
v
i
)
+
1 when ε
G
(
v
i
)
=
1.
Thus the connective eccentric index of double graphG
* is
(8)
C
ξ
G
*
=
∑
i
=
1
n
‍
d
G
*
x
i
ε
G
*
x
i
+
∑
i
=
1
n
‍
d
G
*
y
i
ε
G
*
y
i
=
2
∑
ε
G
(
v
i
)
≥
2
‍
2
d
G
v
i
ε
G
v
i
+
∑
ε
G
v
i
=
1
‍
2
d
G
v
i
ε
G
v
i
+
1
=
4
∑
ε
G
(
v
i
)
≥
2
‍
d
G
v
i
ε
G
v
i
+
∑
ε
G
v
i
=
1
‍
d
G
v
i
2
=
4
∑
ε
G
(
v
i
)
≥
2
‍
d
G
v
i
ε
G
v
i
+
∑
ε
G
(
v
i
)
=
1
‍
d
G
v
i
1
-
2
∑
ε
G
(
v
i
)
=
1
‍
d
G
v
i
=
4
C
ξ
(
G
)
-
2
(
n
-
1
)
n
-
1
G
.LetG
=
(
V
,
E
) be a simple connected graph with V
=
v
1
,
v
2
,
…
,
v
n. The extended double cover of G, denoted by G
*
*, is the bipartite graph with bipartition (
X
,
Y
) where X
=
x
1
,
x
2
,
…
,
x
n and Y
=
y
1
,
y
2
,
…
,
y
n in which x
i and y
j are adjacent if and only if either v
i and v
j are adjacent in G or i
=
j. For example, the extended double cover of the complete graph is the complete bipartite graph. This construction of the extended double cover was introduced by Alon [13] in 1986. Extended double cover of P
3 is illustrated in Figure 2.Figure 2
The graphP
3 and its extended double cover P
3
*
*.Theorem 7.
The connective eccentric index of the extended double coverG
*
* satisfies the inequality
(9)
C
ξ
G
*
*
<
2
C
ξ
G
-
n
n
-
1
G
-
2
.Proof.
IfG is a graph with n vertices and m edges, then, from definition, the extended double cover graph G
*
* consists of 2
n vertices and (
n
+
2
m
) edges and d
G
*
*
(
x
i
)
=
d
G
*
*
(
y
i
)
=
d
G
(
v
i
)
+
1 and ε
G
*
(
x
i
)
=
ε
G
*
(
y
i
)
=
ε
G
(
v
i
)
+
1 for i
=
1,2
,
…
,
n.
Thus the connective eccentric index of extended double cover graphG
*
* is given by
(10)
C
ξ
G
*
*
=
∑
i
=
1
n
‍
d
G
*
*
x
i
ε
G
*
*
x
i
+
∑
i
=
1
n
‍
d
G
*
y
i
ε
G
*
y
i
=
2
∑
ε
G
(
v
i
)
>
1
‍
d
G
v
i
+
1
ε
G
v
i
+
1
+
∑
ε
G
(
v
i
)
=
1
‍
d
G
v
i
+
1
2
<
2
∑
ε
G
(
v
i
)
>
1
‍
d
G
v
i
+
1
ε
G
v
i
+
∑
ε
G
(
v
i
)
=
1
‍
d
G
v
i
+
1
=
2
∑
ε
G
(
v
i
)
>
1
‍
d
G
v
i
ε
G
v
i
+
∑
ε
G
(
v
i
)
>
1
‍
1
ε
G
v
i
+
∑
ε
G
(
v
i
)
=
1
‍
d
G
v
i
+
∑
ε
G
(
v
i
)
=
1
‍
1
=
2
∑
ε
G
(
v
i
)
>
1
‍
d
G
v
i
ε
G
v
i
+
∑
ε
G
(
v
i
)
=
1
‍
d
G
v
i
+
2
∑
ε
G
(
v
i
)
>
1
‍
1
ε
G
v
i
-
∑
ε
G
(
v
i
)
=
1
‍
d
G
v
i
+
∑
ε
G
(
v
i
)
=
1
‍
1
=
2
C
ξ
G
+
2
n
-
n
-
1
G
-
n
-
1
n
-
1
G
+
n
-
1
G
=
2
C
ξ
(
G
)
-
n
n
-
1
G
-
2
.Now some exact formulae for the eccentric connectivity index of joins, symmetric difference, disjunction, and splice graphs are presented.


## 2.2. Join

The joinG
1
+
G
2 of two graphs G
1 and G
2, with disjoint vertex sets V
1, V
2 and edge sets E
1, E
2, is the graph union G
1
∪
G
2 together with all the edges joining V
1 and V
2; that is, G
1
+
G
2 consists of the vertex set V
1
∪
V
2 and edge set E
1
∪
E
2
∪
{
x
y
:
x
∈
V
1
,
y
∈
V
2
}.Theorem 8.
LetG
1 and G
2 be two graphs without well-connected vertices. Then, C
ξ
(
G
1
+
G
2
)
=
|
E
(
G
1
)
|
+
|
E
(
G
2
)
|
+
|
V
G
1
|
|
V
(
G
2
)
|.Proof.
Letn
1 and n
2 be the numbers of vertices in G
1 and G
2, respectively. Thus, |
V
(
G
1
+
G
2
)
|
=
|
V
1
|
+
|
V
2
|
=
n
1
+
n
2. For vertices u
∈
V
1 and v
∈
V
2, it holds that d
G
1
+
G
2
(
u
)
=
d
G
1
(
u
)
+
n
2 and d
G
1
+
G
2
(
v
)
=
d
G
2
(
v
)
+
n
1. Since none of G
1 and G
2 contains well-connected vertices, then, for every u
∈
V
(
G
1
+
G
2
), ε
G
1
+
G
2
(
u
)
=
2. So, from definition of connective eccentric index, we have
(11)
C
ξ
G
1
+
G
2
=
∑
v
∈
V
(
G
1
)
‍
d
G
1
+
G
2
v
ε
G
1
+
G
2
v
+
∑
v
∈
V
(
G
2
)
‍
d
G
1
+
G
2
v
ε
G
1
+
G
2
v
=
1
2
∑
v
∈
V
(
G
1
)
‍
d
G
1
(
v
)
+
n
2
+
∑
v
∈
V
(
G
2
)
‍
d
G
2
(
v
)
+
n
1
from where the desired result follows.Now we generalize the above result forn disjoint graphs G
1
,
G
2
,
…
,
G
n.Theorem 9.
LetG
1
,
G
2
,
…
,
G
n be n graphs with disjoint vertex sets V
i
=
V
(
G
i
) and edge sets E
i
=
E
(
G
i
), 1
≤
i
≤
n, without well-connected vertices. Then,
(12)
C
ξ
G
1
+
G
2
+
⋯
+
G
n
=
∑
i
=
1
n
‍
E
G
i
+
1
2
∑
i
=
1
n
‍
V
G
i
2
-
1
2
∑
i
=
1
n
‍
V
G
i
2
.Proof.
From definition of join, we haved
G
1
+
G
2
+
⋯
+
G
n
(
v
j
)
=
d
G
i
(
v
j
)
+
|
V
(
G
1
+
G
2
+
⋯
+
G
n
)
|
-
|
V
(
G
i
)
| and since none of G
1
,
G
2
,
…
,
G
n contains any well-connected vertex, we have ε
G
1
+
G
2
+
⋯
+
G
n
(
v
j
)
=
2 for all v
j
∈
V
(
G
i
).
Thus the connective eccentric index ofG
1
+
G
2
+
⋯
+
G
n is given by
(13)
C
ξ
G
1
+
G
2
+
⋯
+
G
n
=
∑
i
=
1
n
‍
∑
j
=
1
V
(
G
i
)
‍
d
G
1
+
G
2
+
⋯
+
G
n
v
j
ε
G
1
+
G
2
+
⋯
+
G
n
v
j
=
∑
i
=
1
n
‍
∑
j
=
1
V
(
G
i
)
‍
d
G
i
v
j
+
V
G
1
+
G
2
+
⋯
+
G
n
-
V
G
i
2
=
1
2
E
G
1
+
E
G
2
+
⋯
+
E
G
n
V
G
1
2
+
V
G
2
2
+
⋯
+
V
G
n
2
+
V
G
1
+
G
2
+
⋯
+
G
n
×
V
G
1
+
V
G
2
+
⋯
+
V
G
n
-
V
G
1
2
+
V
G
2
2
+
⋯
+
V
G
n
2
from where the desired result follows.The following corollaries are direct consequences of the theorem.Corollary 10.
Ifn
G denotes the join of n copies of G, then
(14)
C
ξ
(
n
G
)
=
n
E
G
+
n
(
n
-
1
)
2
V
G
2
.Corollary 11.
LetG
=
K
m
1
,
m
2
,
…
,
m
n be the complete n-partite graph [see Figure 3] having v
=
|
V
(
G
)
| number of vertices. Here the vertex set can be partitioned into n subsets V
1
,
V
2
,
…
,
V
n such that V
1
∪
V
2
∪
⋯
∪
V
n
=
V
(
G
) and V
i
∩
V
j
=
ϕ, i
≠
j, 1
≤
i, j
≤
n. From definition of join it is clear that G
=
K
m
1
,
m
2
,
…
,
m
n is the join of n empty graphs with m
1
,
m
2
,
…
,
m
n number of vertices. Then the connective eccentric index of G
=
K
m
1
,
m
2
,
…
,
m
n is given by
(15)
C
ξ
(
K
m
1
,
m
2
,
…
,
m
n
)
=
∑
1
≤
i
≤
n
1
≤
j
≤
n
i
≠
j
‍
m
i
m
j
.Figure 3
The completen-partite graph.


## 2.3. Symmetric Difference

LetG
1 and G
2 be two graphs with vertex sets V
(
G
1
) and V
(
G
2
) and edge sets E
(
G
1
) and E
(
G
2
). Then the symmetric difference of G
1 and G
2, denoted by G
1
⊕
G
2, is the graph with vertex set V
(
G
1
)
×
V
(
G
2
) in which any two vertices (
u
1
,
u
2
) are adjacent to (
v
1
,
v
2
) whenever u
1 is adjacent to v
1 in G
1 or u
2 is adjacent to v
2 in G
2, but not both. From definition of symmetric difference, the degree of a vertex (
u
1
,
u
2
) of G
1
⊕
G
2 is given by [12]
(16)
d
G
1
⊕
G
2
u
1
,
u
2
=
V
G
2
d
G
1
u
1
+
V
G
1
d
G
2
u
2
-
2
d
G
1
(
u
1
)
d
G
2
(
u
2
)
.Theorem 12.
The connective eccentric index of the symmetric differenceG
1
⊕
G
2 of two graphs G
1 and G
2 is given by
(17)
C
ξ
G
1
⊕
G
2
=
E
G
1
V
G
2
2
+
E
G
2
V
G
1
2
-
4
E
G
1
E
G
2
,
where none of G
1 and G
2 contains well-connected vertices.Proof.
Since the distance between any two vertices of a symmetric difference cannot exceed two, if none of the components contains well-connected vertices, the eccentricity of all vertices is constant and is equal to two; that is,ε
G
1
⊕
G
2
(
u
1
,
u
2
)
=
2, for all vertices (
u
1
,
u
2
) [7, 8].
Thus the connective eccentric index of symmetric differenceG
1
⊕
G
2 of two graphs G
1 and G
2 is given by
(18)
C
ξ
G
1
⊕
G
2
=
∑
(
u
1
,
u
2
)
∈
V
(
G
1
⊕
G
2
)
‍
d
G
1
⊕
G
2
u
1
,
u
2
ε
G
1
⊕
G
2
u
1
,
u
2
=
1
2
∑
u
1
∈
V
(
G
1
)
‍
∑
u
2
∈
V
(
G
2
)
‍
V
G
2
d
G
1
u
1
+
V
G
1
d
G
2
u
2
-
2
d
G
1
u
1
d
G
2
u
2
V
G
1
=
1
2
V
G
2
2
∑
u
1
∈
V
(
G
1
)
‍
d
G
1
(
u
1
)
+
V
G
1
2
∑
u
2
∈
V
(
G
2
)
‍
d
G
2
(
u
2
)
-
2
∑
u
1
∈
V
(
G
1
)
‍
d
G
1
(
u
1
)
∑
u
2
∈
V
(
G
2
)
‍
d
G
2
(
u
2
)
from where the desired result follows.


## 2.4. Disjunction

The disjunctionG
1
∨
G
2 of two graphs G
1 and G
2 is the graph with vertex set V
(
G
1
)
×
V
(
G
2
) in which (
u
1
,
u
2
) is adjacent to (
v
1
,
v
2
) whenever u
1 is adjacent to v
1 in G
1 or u
2 is adjacent to v
2 in G
2. Obviously, the degree of a vertex (
u
1
,
u
2
) of G
1
∨
G
2 is given by [7, 8]
(19)
d
G
1
∨
G
2
u
1
,
u
2
=
V
G
2
d
G
1
(
u
1
)
+
V
G
1
d
G
2
v
2
-
d
G
1
u
1
d
G
2
v
2
.Theorem 13.
The connective eccentric index of the disjunctionG
1
∨
G
2 of two graphs G
1 and G
2 is given by
(20)
C
ξ
G
1
∨
G
2
=
E
G
1
V
G
2
2
+
E
G
2
V
G
1
2
-
2
E
G
1
E
G
2
,
where none of G
1 and G
2 contains well-connected vertices.Proof.
Since the distance between any two vertices of a disjunction cannot exceed two, if none of the components contains well-connected vertices, the eccentricity of all vertices is constant and equal to two [7, 8]. Then the connective eccentric index of the disjunction G
1
∨
G
2 of two graphs G
1 and G
2 is computed as
(21)
C
ξ
G
1
∨
G
2
=
∑
(
u
i
,
v
j
)
∈
V
(
G
1
∨
G
2
)
‍
d
G
1
∨
G
2
u
1
,
u
2
ε
G
1
∨
G
2
u
1
,
u
2
=
1
2
∑
u
1
∈
V
(
G
1
)
‍
∑
v
2
∈
V
(
G
2
)
‍
V
G
2
d
G
1
u
1
+
V
G
1
d
G
2
u
2
-
d
G
1
(
u
1
)
d
G
2
(
u
2
)
from where the desired result follows.


## 2.5. Splice

LetG
1
=
(
V
1
,
E
1
) and G
2
=
(
V
2
,
E
2
) be two graphs V
1
∩
V
2
=
ϕ. Let v
1
∈
V
1 and v
2
∈
V
2 be two given vertices of G
1 and G
2, respectively. A splice of G
1 and G
2 at the vertices v
1 and v
2 is obtained by identifying the vertices v
1 and v
2 in the union of G
1 and G
2 and is denoted by S
(
G
1
,
G
2
,
v
1
,
v
2
) [15]. Different topological indices of the splice graphs have already been computed [16]. Let u
∈
V
(
S
); then ε
1
(
u
) denotes the eccentricity of u as a vertex of G
1
,
ε
2
(
u
) denotes the eccentricity of u as a vertex of G
2, and ɛ
(
u
) denotes the eccentricity of u as a vertex of S. Let d
S
(
x
) be the degree of the vertex x
∈
V
(
S
). Then the connective eccentric index of S
(
G
1
,
G
2
,
v
1
,
v
2
) is computed as follows.Theorem 14.
The connective eccentric index of splice ofG
1 and G
2 is given by
(22)
C
ξ
S
=
∑
x
∈
V
1
‍
d
S
x
max
⁡
d
G
1
x
,
v
1
+
ε
1
x
ε
2
v
2
+
∑
y
∈
V
2
‍
d
S
(
y
)
max
⁡
d
G
2
(
y
,
v
2
)
+
ε
1
(
v
1
)
ε
2
(
y
)
.Proof.
For any vertexx
∈
V
1, Sharafdini and Gutman [16] showed that
(23)
ɛ
(
x
)
=
max
⁡
d
G
1
(
x
,
v
1
)
+
ε
1
(
x
)
ε
2
(
v
2
)
.
Similarly, for any vertex y
∈
V
2,
(24)
ɛ
(
y
)
=
max
⁡
d
G
2
(
y
,
v
2
)
+
ε
1
(
v
1
)
ε
2
(
y
)
.
Thus, the desired result follows from the definition of connective eccentric index.



---

*Source: 579257-2014-12-24.xml*