# Eccentric Connectivity and Zagreb Coindices of the Generalized Hierarchical Product of Graphs

Authors: M. Tavakoli; F. Rahbarnia; A. R. Ashrafi
Journal: Journal of Discrete Mathematics
 (2014)

---

## Abstract

Formulas for calculations of the eccentric connectivity index and Zagreb coindices of graphs under generalized hierarchical product are presented. As an application, explicit formulas for eccentric connectivity index and Zagreb coindices of some chemical graphs are obtained.


---

## Body

## 1. Introduction

All graphs considered here are undirected, simple, and connected. For two verticesu and v of a graph G, the distance d
(
u
,
v
) is equal to the length of a shortest path connecting u and v. Suppose that V
(
G
) and E
(
G
) are the set of vertices and edges of G, respectively. For every vertex u
∈
V
(
G
), the edge connecting u and v is denoted by u
v and deg
⁡
G
(
u
) (deg
⁡
(
u
) for short) denotes the degree of u in G. The diameter of G, denoted by diam
⁡
(
G
), is the maximum distance among all pairs of vertices in the graph.The first and second Zagreb indices are defined as(1)
M
1
G
=
∑
u
∈
V
G
deg
⁡
u
2
,
M
2
G
=
∑
u
v
∈
E
G
deg
⁡
u
2
deg
⁡
v
,
respectively [1]. The applications of these graph invariants and their mathematical properties are reviewed in two important survey articles [2, 3]. When a topological index or a new graph operation is introduced, then the following mathematical questions are usually raised.(1)
What are the extremal properties of this new topological index?
(2)
Is it possible to find exact formulas for this topological index under old and new graph operations?We refer to [4–7] for such questions about Zagreb group indices.The Zagreb indices can be viewed as the contributions of pairs of adjacent vertices to certain degree-weighted generalizations of Wiener polynomials. The first and second Zagreb coindices were first introduced by Došlić [8]. They are defined as follows:
(2)
M
-
1
G
=
∑
u
v
∉
E
G
deg
⁡
u
+
deg
⁡
v
,
M
-
2
G
=
∑
u
v
∉
E
G
deg
⁡
⁡
u
deg
⁡
⁡
v
.
In [9], the authors computed exact formulas for these graph parameters under some graph operations.Now we define a vertex version of Zagreb indices as follows:(3)
M
-
1
*
G
=
∑
u
,
v
⊆
V
G
deg
⁡
u
+
deg
⁡
v
,
M
-
2
*
G
=
∑
u
,
v
⊆
V
G
deg
⁡
u
deg
⁡
v
.
The graph invariants M
-
1
*
(
G
) and M
-
2
*
(
G
) are called the first and second vertex Zagreb indices of G.The eccentricityε
G
(
u
) is the largest distance between u and any other vertex v of G. The total connectivity index ζ
(
G
) of a graph G is defined as ζ
(
G
)
=
∑
u
∈
V
(
G
)
‍
ε
G
(
u
). Also, the eccentric connectivity index of G is defined as ξ
c
(
G
)
=
∑
u
∈
V
(
G
)
‍
ε
G
(
u
)
deg
⁡
G
(
u
) [10]. We refer to [11] for a good survey on this topological index.A graphG with a specified vertex subset U
⊆
V
(
G
) is denoted by G
(
U
). Suppose G and H are graphs and U
⊆
V
(
G
). The generalized hierarchical product, denoted by G
(
U
)
⊓
H, is the graph with vertex set V
(
G
)
×
V
(
H
) and two vertices (
g
,
h
) and (
g
′
,
h
′
) are adjacent if and only if g
=
g
′
∈
U and h
h
′
∈
E
(
H
) or g
g
′
∈
E
(
G
) and h
=
h
′; see Figure 1. This graph operation was introduced recently by Barrière et al. [12, 13] and found some applications in computer science. We encourage the reader to consult [14–16] for the mathematical properties of the hierarchical product of graphs. The Cartesian product, G
×
H, of graphs G and H has the vertex set V
(
G
×
H
)
=
V
(
G
)
×
V
(
H
) and (
u
,
x
)
(
v
,
y
) is an edge of G
×
H if u
=
v and x
y
∈
E
(
H
) or u
v
∈
E
(
G
) and x
=
y [17].Figure 1
The molecular graph of truncated cubeH
=
G
(
U
)
⊓
P
2, where U
=
{
v
1
,
v
4
,
v
9
,
v
12
}.We denote byP
n and C
n the path and cycle with n vertices, respectively. Our notations are standard and can be taken from the standard books on graph theory.


## 2. MainResults

We start by introducing some notations that will be kept throughout this section. LetG
=
(
V
,
E
) be a graph and U
⊆
V. Following Pattabiraman and Paulraja [18], an u
-
v path through U in G
(
U
) is an u
-
v path in G containing some vertices w
∈
U (not necessarily distinct from u and v). Let d
G
(
U
)
(
u
,
v
) denote the length of a shortest u
-
v path through U in G. Notice that if one of the vertices u and v belongs to U, then d
G
(
U
)
(
u
,
v
)
=
d
G
(
u
,
v
). Furthermore, let ε
G
U
(
u
)
=
max
⁡
{
d
G
U
u
,
v
∣
v
∈
V
(
G
(
U
)
)
}; then ζ
(
G
(
U
)
) and ξ
c
(
G
(
U
)
) can be defined as follows:
(4)
ζ
G
U
=
∑
u
∈
V
G
U
ε
G
U
u
,
ξ
c
G
U
=
∑
u
∈
V
G
U
ε
G
U
u
deg
⁡
G
u
.Lemma 1 (see [13]).
LetG and H be graphs with U
⊆
V
(
G
). Then one has the following:(a)
ifU
=
V
(
G
), then the generalized hierarchical product G
(
U
)
⊓
H is the Cartesian product of G and H;
(b)
V
G
U
⊓
H
=
V
G
V
H; E
G
U
⊓
H
=
E
G
V
H
+
E
H
U;
(c)
G
(
U
)
⊓
H is connected if and only if G and H are connected;
(d)
d
G
U
⊓
H
(
(
g
,
h
), (
g
′
,
h
′
) = {
d
G
U
(
g
,
g
′
) + d
H
(
h
,
h
′
), if h
≠
h
′; d
G
g
,
g
′, if h
=
h
′
}.Theorem 2 (see [19]).
LetG and H be two connected graphs and let U be a nonempty subset of V
(
G
). Then
(5)
ξ
c
G
U
⊓
H
=
V
H
ξ
c
G
U
+
U
ξ
c
H
+
2
E
H
∑
u
∈
U
ε
G
U
u
+
2
E
G
ζ
H
.PutU
=
V
(
G
). Then G
(
U
)
⊓
H
=
G
×
H, ξ
c
(
G
(
U
)
)
=
ξ
c
(
G
), and ∑
u
∈
U
‍
ε
G
(
U
)
(
u
)
=
ζ
(
G
). Therefore,Corollary 3 (see [19]).
LetG and H be two connected graphs. Then
(6)
ξ
c
G
×
H
=
V
H
ξ
c
G
+
V
G
ξ
c
H
+
2
E
H
ζ
G
+
2
E
G
ζ
H
.Example 4.
LetH be the graph of truncated cube. Then H
=
G
(
U
)
⊓
P
2, where U
=
{
v
1
,
v
4
,
v
9
,
v
12
}, as shown in Figure 1. It is not difficult to check that ∑
u
∈
U
‍
ε
G
(
U
)
(
u
)
=
20, ξ
c
(
G
(
U
)
)
=
160 and so, by Theorem 2, we have ξ
c
(
H
)
=
ξ
c
(
G
(
U
)
⊓
P
2
)
=
2
×
160
+
4
×
2
+
2
×
20
+
2
×
16
×
2
=
432.Example 5.
Consider the linear phenyleneF
n including n
>
1 benzene rings; see Figure 2. The linear phenylene F
n is the graph P
3
n
(
U
)
⊓
P
2, where
(7)
U
=
v
3
k
+
1
∣
0
⩽
k
⩽
n
-
1
∪
v
3
k
∣
1
⩽
k
⩽
n
.
On the other hand, by tedious calculations, one can check that
(8)
U
=
2
n
∑
u
∈
U
ε
P
3
n
U
u
=
9
2
n
2
-
n
+
1
2
2
∤
n
9
2
n
2
-
n
2
∣
n
,
ξ
c
P
3
n
U
=
27
2
n
2
-
9
n
+
3
2
2
∤
n
27
2
n
2
-
9
n
+
2
2
∣
n
.
So, by Theorem 2, we obtain
(9)
ξ
c
F
n
=
ξ
c
P
3
n
U
⊓
P
2
=
36
n
2
-
4
n
.Figure 2
The linear phenyleneF
n
=
P
3
n
(
U
)
⊓
P
2, where U
=
{
v
3
k
+
1
∣
0
⩽
k
⩽
n
-
1
}
∪
{
v
3
k
∣
1
⩽
k
⩽
n
}.Theorem 6.
LetG and H be two connected graphs and let U be a nonempty subset of V
(
G
). Then, (1)
M
-
1
*
(
G
(
U
)
⊓
H
)
=
2
(
V
G
V
H
-
1
)
(
U
E
H
+
V
H
E
G
).
(2)
M
-
2
*
(
G
(
U
)
⊓
H
)
=
V
H
2
M
-
2
*
(
G
)
+
2
E
H
2
|
U
|
(
U
-
1
) + (
1
/
2
)
V
H
(
V
H
-
1
)
M
1
(
G
) + U
M
-
2
*
(
H
)
+
4
V
H
E
H
U
E
G + (
M
-
1
*
(
H
)
-
2
V
H
E
H
)
∑
u
∈
U
‍
deg
⁡
G
(
u
).Proof.
LetG and H be two connected graphs and let U be a nonempty subset of V
(
G
). The part (1) of this theorem is clear. To prove the second part, we notice that by definitions of generalized hierarchical product and M
-
2
*, we have
(10)
M
-
2
*
G
U
⊓
H
=
∑
g
,
h
,
g
′
,
h
′
⊆
V
G
U
⊓
H
deg
⁡
G
U
⊓
H
g
,
h
W
W
W
W
W
W
W
W
W
W
·
deg
⁡
G
U
⊓
H
g
′
,
h
′
=
∑
h
∈
V
H
∑
h
′
∈
V
H
∑
g
∈
U
∑
g
′
∈
V
G
-
U

deg
⁡
G

g
+
deg
⁡
H
h
deg
⁡
G

g
′
W
+
∑
h
∈
V
H
∑
h
′
∈
V
H
∑
g
,
g
′
⊆
U
deg
⁡
G
g
+
deg
⁡
H
h
W
W
W
W
W
W
W
W
W
W
·
deg
⁡
G
g
′
+
deg
⁡
H
h
′
W
+
∑
h
∈
V
H
∑
h
′
∈
V
H
∑
g
,
g
′
⊆
V
G
-
U
deg
⁡
G
g
deg
⁡
G
g
′
W
+
∑
h
,
h
′
⊆
V
H
∑
g
∈
U
deg
⁡
G
g
+
deg
⁡
H
h
W
W
W
W
W
W
W
·
deg
⁡
G
g
+
deg
⁡
H
h
′
W
+
∑
h
,
h
′
⊆
V
H
∑
g
∈
V
G
-
U
deg
⁡
G
g
2
=
V
H
2
∑
g
∈
U
,
g
′
∈
V
G
-
U
deg
⁡
G
g
deg
⁡
G
g
′
W
+
2
V
H
E
H
U
∑
g
′
∈
V
G
-
U
deg
⁡
G
g
′
W
+
V
H
2
∑
g
,
g
′
⊆
U
deg
⁡
G
g
deg
⁡
G
g
′
W
+
2
E
H
2
U
U
-
1
W
+
∑
h
∈
V
H
∑
h
′
∈
V
H
∑
g
,
g
′
⊆
U
deg
⁡
G
g
deg
⁡
H
h
′
W
W
W
W
W
W
W
W
W
W
W
+
deg
⁡
G
g
′
deg
⁡
H
h
W
+
V
H
2
∑
g
,
g
′
⊆
V
G
-
U
deg
⁡
G
g
deg
⁡
G
g
′
W
+
1
2
V
H
V
H
-
1
∑
g
∈
U
deg
⁡
G
g
2
W
+
M
-
1
*
H
∑
g
∈
U
deg
⁡
G
g
+
U
M
-
2
*
H
W
+
1
2
V
H
V
H
-
1
∑
g
∈
V
G
-
U
deg
⁡
G
g
2
=
V
H
2
M
-
2
*
G
+
2
E
H
2
U
U
-
1
W
+
1
2
V
H
V
H
-
1
M
1
G
W
+
U
M
-
2
*
H
+
4
V
H
E
H
U
E
G
W
+
M
-
1
*
H
-
2
V
H
E
H
∑
u
∈
U
deg
⁡
G
u
.
This completes the proof.Corollary 7 (see [15]).
LetG and H be two connected graphs and let U be a nonempty subset of V
(
G
). Then
(11)
M
1
G
U
⊓
H
=
V
H
M
1
G
+
U
M
1
H
+
4
E
H
∑
u
∈
U
deg
⁡
G
u
.Proof.
It follows from definition ofM
-
2
* that M
1
(
G
(
U
)
⊓
H
)
=
4
E
G
U
⊓
H
2
-
2
M
-
2
*
(
G
(
U
)
⊓
H
). On the other hand, E
G
U
⊓
H
=
V
H
E
H
+
U
E
G. Therefore,
(12)
M
1
G
U
⊓
H
=
4
V
H
2
E
G
2
+
4
U
2
E
H
2
-
2
V
H
2
M
-
2
*
G
-
4
E
H
2
U
U
-
1
-
V
H
V
H
-
1
M
1
G
-
2
U
M
-
2
*
H
-
2
M
-
1
*
H
-
2
V
H
E
H
∑
u
∈
U
deg
⁡
G
u
.
So, by replacing M
-
1
*
(
G
) and M
-
2
*
(
G
) with 2
E
G
(
V
G
-
1
) and M
-
2
*
(
G
)
=
2
E
G
2
-
(
1
/
2
)
M
1
(
G
), respectively, in the above equation, the assertion follows immediately.Corollary 8.
LetG and H be two connected graphs and let U be a nonempty subset of V
(
G
). Then
(13)
M
-
1
G
U
⊓
H
=
2
V
G
V
H
-
1
·
U
E
H
+
V
H
E
G
-
V
H
M
1
G
-
U
M
1
H
-
4
E
H
∑
u
∈
U
deg
⁡
G
u
.Proof.
The assertion follows from Theorem6, Corollary 7, and the fact that M
-
1
(
G
(
U
)
⊓
H
) = M
-
1
*
(
G
(
U
)
⊓
H
)
-
M
1
(
G
(
U
)
⊓
H
).Theorem 9 (see [15]).
LetG and H be two connected graphs and let U be a nonempty subset of V
(
G
). Then
(14)
M
2
G
U
⊓
H
=
V
H
M
2
G
+
U
M
2
H
+
2
E
H
∑
u
∈
U
∑
x
∈
N
u
deg
⁡
G
x
+
M
1
H
x
y
∈
E
G
∣
x
,
y
∈
U
+
E
H
∑
u
∈
U
deg
⁡
G
u
2
+
M
1
H
∑
u
∈
U
deg
⁡
G
u
,
where N
[
u
] is the set of all adjacent vertices of u.By Theorems6 and 9 and this fact that M
-
2
(
G
(
U
)
⊓
H
)
=
M
-
2
*
(
G
(
U
)
⊓
H
)
-
M
2
(
G
(
U
)
⊓
H
), we can write the following.Corollary 10.
LetG and H be two connected graphs and let U be a nonempty subset of V
(
G
). Then
(15)
M
-
2
G
U
⊓
H
=
V
H
2
M
-
2
*
G
+
2
E
H
2
U
U
-
1
W
+
1
2
V
H
V
H
-
1
M
1
G
+
U
M
-
2
*
H
W
+
4
V
H
E
H
U
E
G
W
+
M
-
1
*
H
-
M
1
H
-
2
V
H
E
H
W
·
∑
u
∈
U
deg
⁡
G
u
-
V
H
M
2
G
W
-
U
M
2
H
-
2
E
H
∑
u
∈
U
∑
x
∈
N
u
deg
⁡
G
x
-
M
1
H
W
·
x
y
∈
E
G
∣
x
,
y
∈
U
-
E
H
∑
u
∈
U
deg
⁡
G
u
2
.Example 11.
The molecular graph of dimer fullereneH is the graph C
60
(
U
)
⊓
P
2, where U
=
{
5,6
} (Figure 3). On the other hand, it is not difficult to check that M
1
(
C
60
)
=
540, M
2
(
C
60
)
=
810, ∑
u
∈
U
‍
deg
⁡
C
60
(
u
)
=
6, ∑
u
∈
U
‍
deg
⁡
C
60
(
u
)
2
=
18, ∑
u
∈
U
‍
∑
x
∈
N
[
u
]
‍
deg
⁡
C
60
(
x
)
=
18, M
-
2
*
(
C
60
)
=
15930, and {
x
y
∈
E
C
60
∣
x
,
y
∈
U
}
=
1. Thus, by the above results, we obtain(1)
M
-
1
*
(
C
60
(
U
)
⊓
P
2
)
=
43316 and M
-
2
*
(
C
60
(
U
)
⊓
P
2
)
=
65694.
(2)
M
-
1
(
C
60
(
U
)
⊓
P
2
)
=
42208 and M
-
2
(
C
60
(
U
)
⊓
P
2
)
=
64004.Figure 3
The dimer fullereneC
60.Example 12.
Consider the linear phenyleneF
n including n benzene rings (Figure 2). The linear phenylene F
n is the graph P
3
n
(
U
)
⊓
P
2, where U
=
{
v
3
k
+
1
∣
0
⩽
k
⩽
n
-
1
}
∪
{
v
3
k
∣
1
⩽
k
⩽
n
}; see Figure 2. On the other hand, it is not difficult to check that M
1
(
P
3
n
)
=
12
n
-
6, M
2
(
P
3
n
)
=
12
n
-
8, ∑
u
∈
U
‍
deg
⁡
P
3
n
(
u
)
=
4
n
-
2, ∑
u
∈
U
‍
deg
⁡
P
3
n
(
u
)
2
=
8
n
-
6, ∑
u
∈
U
‍
∑
x
∈
N
[
u
]
‍
deg
⁡
P
3
n
(
x
)
=
8
n
-
4, M
-
2
*
(
P
3
n
)
=
18
n
2
-
18
n
+
5, and {
x
y
∈
E
P
3
n
∣
x
,
y
∈
U
}
=
n
-
1. Hence, by previous result, we obtain the following:(1)
M
-
1
*
(
F
n
)
=
M
-
1
*
(
P
3
n
(
U
)
⊓
P
2
)
=
96
n
2
-
40
n
+
4 and M
-
2
*
(
F
n
)
=
M
-
2
*
(
P
3
n
(
U
)
⊓
P
2
)
=
128
n
2
-
86
n
+
18;
(2)
M
-
1
(
F
n
)
=
M
-
1
(
P
3
n
(
U
)
⊓
P
2
)
=
96
n
2
-
84
n
+
24 and M
-
2
(
F
n
)
=
M
-
2
(
P
3
n
(
U
)
⊓
P
2
) = 128
n
2
-
146
n
+
54.Example 13.
LetH be the graph of truncated cube. Then H
=
G
(
U
)
⊓
P
2, where U
=
{
v
1
,
v
4
,
v
9
,
v
12
}, as shown in Figure 1. Therefore,(1)
M
-
1
*
(
G
(
U
)
⊓
P
2
)
=
1656 and M
-
2
*
(
P
3
n
(
U
)
⊓
P
2
)
=
2484.
(2)
M
-
1
(
P
3
n
(
U
)
⊓
P
2
)
=
1440 and M
-
2
(
G
(
U
)
⊓
P
2
)
=
2160.



---

*Source: 292679-2014-11-27.xml*