# Sharp Bounds of the Hyper-Zagreb Index on Acyclic, Unicylic, and Bicyclic Graphs

Authors: Wei Gao; Muhammad Kamran Jamil; Aisha Javed; Mohammad Reza Farahani; Shaohui Wang; Jia-Bao Liu
Journal: Discrete Dynamics in Nature and Society
 (2017)

---

## Abstract

The hyper-Zagreb index is an important branch in the Zagreb indices family, which is defined as∑
u
v
∈
E
(
G
)
‍
(
d
(
u
)
+
d
(
v
)
)
2, where d
(
v
) is the degree of the vertex v in a graph G
=
(
V
(
G
)
,
E
(
G
)
). In this paper, the monotonicity of the hyper-Zagreb index under some graph transformations was studied. Using these nice mathematical properties, the extremal graphs among n-vertex trees (acyclic), unicyclic, and bicyclic graphs are determined for hyper-Zagreb index. Furthermore, the sharp upper and lower bounds on the hyper-Zagreb index of these graphs are provided.


---

## Body

## 1. Introduction

A topological indexT
o
p
(
G
) of a graph G is a number with this property that, for every graph H isomorphic to G, Top(H) = Top(G). In 1947, Wiener determined the most widely known topological descriptor, the Wiener index [1]. He used it to determine physical properties of paraffin. The Wiener index of a graph is equal to the sum of distances between all pairs of vertices of related graphs. Numerous indices have been explored. The Zagreb indices are the most important topological indices, introduced by Gutman and Trinajstić more than thirty years ago [2]. For a graph G
=
(
V
,
E
), the first and second Zagreb indices, M
1 and M
2, respectively, are defined as (1)
M
1
G
=
∑
v
∈
V
d
v
2
,
M
2
G
=
∑
u
v
∈
E
d
u
d
v
.In 1972, Zagreb indices first appeared in the topological formulas for the total π-energy of conjugated molecules [2]. For applications in QSPR/QSAR, latest results are referred to [3–8].In 2004, Miličević et al. [9] reformulated Zagreb indices in terms of edge-degrees instead of vertex-degree as follows: (2)
E
M
1
G
=
∑
e
∈
E
d
e
2
,
E
M
2
G
=
∑
e
~
f
d
e
d
f
,where d
(
e
) is the degree of the edge e in G, defined by d
(
e
)
=
d
(
u
)
+
d
(
v
)
-
2 with e
=
u
v, and e
~
f means that the edges e and f are adjacent. Some results related to E
M
1
(
G
) and E
M
2
(
G
) are given in [10–12].In 2013, Shirdel et al. [13] introduced a new degree-based topological index named hyper-Zagreb index as (3)
H
M
G
=
∑
u
v
∈
E
d
u
+
d
v
2
.Recently, the multiplicative versions of Zagreb indices are studied well in [14]. Motivated by these results [15–18], we explore the properties for the hyper-Zagreb index.LetG be a simple and connected graph with vertex set V and edge set E. For a vertex v
∈
V, N
G
(
v
) denotes the set of all neighbors of v in G. In a graph G, the number of independent cycles is called its cyclomatic number and is equal to γ
=
m
-
n
+
1. Recall that graphs with γ
=
0,1
,
2 are referred to as trees, unicyclic graphs, and bicyclic graphs, respectively. S
n, P
n, and C
n denote the star, path, and cycle on n vertices, respectively. Let v
∈
V, and then let G
-
v be a subgraph of G by deleting vertex v and adjacent edges. For e
∈
E, let G
-
e be a subgraph of G by deleting an edge e. Let G be a nontrivial graph and let v be its vertex. If K is obtained from G by fusing a tree T at v, then we say that T is a subtree of K and u is its root. The fusions of two vertices u and v in G are denoted by u
+
v. In order to exhibit our results, we introduce some graph-theoretical notations and terminology. For other undefined ones, see the book [19].In this paper, we characterize the extremal properties of the hyper-Zagreb index. In Section2, we present some graph transformations which increase or decrease H
M. In Section 3, we determine the extremal acyclic, unicyclic, and bicyclic graphs with maximum and minimum hyper-Zagreb index.


## 2. Graph Transformations

In this section, we will introduce some graph transformations, which increase or decrease the hyper-Zagreb index. These transformations will help to prove our main results. The following one fromG to H strictly decreases the hyper-Zagreb index of a graph.Transformation 1.
LetG be a nontrivial connected graph and v is a given vertex in G. Let H be a graph obtained from G by attaching two paths: P
1
=
v
u
1
u
2
⋯
u
a of length a and P
2
=
v
w
1
w
2
⋯
w
b of length b. If H
=
G
-
v
w
1
+
u
a
w
1, we say that H is obtained from G by Transformation 1, as shown in Figure 1.Figure 1
Two graphs.Lemma 1.
IfH is obtained from G by Transformation 1 as shown in Figure 1, then (4)
H
M
H
<
H
M
G
.Proof.
In applying Transformation1, the degree of v decreases and the degrees of all its neighbors remain unchanged. So,(5)
H
M
G
-
H
M
H
>
d
G
v
+
d
G
w
1
2
+
d
G
v
+
d
G
u
1
2
+
d
G
u
k
+
d
G
u
k
-
1
2
-
d
G
v
-
1
+
d
G
u
1
2
-
d
G
u
k
+
1
+
d
G
u
k
-
1
2
+
d
K
u
k
+
d
G
w
1
2
=
d
G
v
+
2
2
+
d
G
v
+
2
2
+
3
2
-
d
G
v
+
1
2
-
4
2
=
d
G
v
2
+
6
d
G
v
>
0
.Transformation 2.
Letu
v be an edge of connected graph G with d
G
(
v
)
≥
2. Suppose that {
v
,
w
1
,
w
2
,
…
,
w
t
} are all the neighbors of vertex u, while w
1
,
w
2
,
…
,
w
t are pendant vertices. If K
=
G
-
{
u
w
1
,
u
w
2
,
…
,
u
w
t
}
+
{
v
w
1
,
v
w
2
,
…
,
v
w
t
}, we say that K is obtained from G by Transformation 2, as shown in Figure 2.Figure 2
Transformation2.Transformation2 from G to K strictly increases H
M of a graph.Lemma 2.
If K is obtained fromG by Transformation 2 as shown in Figure 2, then (6)
H
M
G
<
H
M
K
.Proof.
Clearly,d
G
(
v
)
<
d
K
(
v
) and (
d
(
u
)
+
d
(
v
)
) is not changed during Transformation 2. Hence, (7)
H
M
K
-
H
M
G
>
t
+
1
d
G
v
+
t
+
1
2
-
d
G
v
+
d
G
u
2
-
t
d
G
u
+
1
2
=
t
+
1
d
G
v
+
t
+
1
2
-
d
G
v
+
t
+
1
2
-
t
t
+
2
2
=
t
d
G
v
+
t
+
1
2
-
t
t
+
2
2
>
0
.Transformation 3.
LetG be nontrivial connected graph and u
,
v
∈
V
(
G
). Let P
a
=
(
u=)
v
1
v
2
⋯
v
a
(=v
) be a nontrivial a-length path of G connecting vertices u and v. If K
=
G
-
{
v
1
v
2
,
v
2
v
3
,
…
,
v
a
-
1
v
a
}
+
{
(
u
+
v
=
)
w
v
1
,
w
v
2
,
…
,
w
v
a
}, we say that K is obtained from G by Transformation 3, as shown in Figure 3.Figure 3
Transformation3.Lemma 3.
IfK is obtained from G by Transformation 3 as shown in Figure 3, then (8)
H
M
K
>
H
M
G
.Proof.
From Figure3, let d
G
1
(
u
)
=
x and d
G
2
(
v
)
=
y, while w
=
u
+
v (merge u and v to obtain w) with d
K
(
w
)
=
x
+
y
+
a
-
1, where a
≥
2. If a
=
2, then (9)
H
M
K
-
H
M
G
>
x
+
y
+
2
-
1
+
1
2
-
x
+
y
+
2
2
=
0
.If a
≥
3, then(10)
H
M
K
-
H
M
G
>
a
-
1
x
+
y
+
a
-
1
+
1
2
-
x
+
3
2
-
y
+
3
2
+
16
a
-
3
=
a
-
1
x
+
y
+
a
2
-
x
+
3
2
-
y
+
3
2
-
16
a
-
3
>
x
+
y
+
a
2
-
x
+
3
2
+
x
+
y
+
a
2
-
y
+
3
>
0
.Transformation 4.
LetH be a nontrivial acyclic subgraph of G with |
H
|
=
t which is attached at u
1 in graph G; let u and v be two neighbors of u
1 different from those in H; also d
(
u
)
=
x and d
(
v
)
=
y. If K
=
G
-
(
H
-
u
1
)
+
u
1
u
2
+
u
2
u
3
+
⋯
+
u
t
v, we say that K is obtained from G by Transformation 4, as shown in Figure 4.Figure 4
Transformation4.Lemma 4.
Let G and K be two graphs, as shown in Figure4. Then (11)
H
M
G
>
H
M
K
.Proof.
From Transformation2, we know that H
M
(
G
)
≥
H
M
(
G
1
). So, we only prove the following inequality:(12)
H
M
G
1
>
H
M
K
,
H
M
G
1
-
H
M
K
=
d
G
1
u
t
-
1
+
d
G
1
u
t
2
+
d
G
1
u
1
+
d
G
1
u
2
2
+
d
G
1
u
+
d
G
1
u
1
2
+
d
G
1
v
+
d
G
1
u
1
2
-
d
K
u
t
-
1
+
d
K
u
t
2
-
d
K
u
1
+
d
K
u
2
2
-
d
K
u
+
d
G
1
u
1
2
-
d
K
v
+
d
K
u
1
2
=
x
+
3
2
+
y
+
3
2
-
x
+
2
2
-
y
+
2
2
+
2
>
0
.Therefore, the proof is complete.LetG be a nontrivial connected graph. Two vertices u and v are said to be equivalent if G
-
u
≅
G
-
v. Clearly, |
N
(
u
)
|
=
|
N
(
v
)
| and their neighbors have the same degree sequence.Transformation 5.
LetG
0 be a nontrivial connected graph and u and v are equivalent vertices in G
0 such that d
G
0
(
u
)
=
d
G
(
v
)
=
x. Let G be the graph obtained by attaching S
a
+
1 and S
b
+
1 at the vertices u and v of G
0, respectively, with a
≥
b
≥
1. If K is the graph obtained by deleting the b pendant vertices at v in G and connecting them to u of G, respectively, as shown in Figure 5. We say that K is obtained from G by Transformation 5.Figure 5
Transformation5.Lemma 5.
If K is obtained fromG by Transformation 5 as shown in Figure 5, then (13)
H
M
G
<
H
M
K
.Proof.
We have(14)
H
M
K
-
H
M
G
>
a
d
K
u
+
1
2
+
b
d
K
u
+
1
2
-
a
d
G
u
+
1
2
-
b
d
G
u
+
1
2
=
a
x
+
a
+
b
+
1
2
+
b
x
+
a
+
b
+
1
2
-
a
x
+
a
+
1
2
-
b
x
+
b
+
1
2
>
0
.


## 3. Main Results

In this section, we characterized the extremal graph with respect toH
M
(
G
) among acyclic, unicyclic, and bicyclic graphs. First, we will define some notations which will be used later. B
n denotes the set of all connected bicyclic graphs with order n. Now we define three special classes of graphs. Let P
n
k
,
l
,
m be the graph obtained by connecting two cycles C
k and C
m with a path P
l with k
+
l
+
m
-
2
=
n. Let C
n
(
p
,
q
) be the graph which contains only two cycles C
p and C
q having a common vertex with p
+
q
-
1
=
n, and let C
n
(
l
,
r
,
t
) be the graph obtained by fusing two triples of pendant vertices of three paths P
l, P
r, and P
t to two vertices with l
+
r
+
t
-
4
=
n, where 2
≤
l
≤
r
≤
t without loss of generality. Let G be a bicyclic graph containing one of the three graphs P
n
k
,
l
,
m, C
n
(
p
,
q
), and C
n
(
l
,
r
,
t
) as its subgraph; then we will call it a brace of G. We set B
n
1, B
n
2, and B
n
3 to be the set of all bicyclic graphs which include P
n
k
,
l
,
m, C
n
(
p
,
q
), and C
n
(
l
,
r
,
t
) as their brace, respectively. Clearly, B
n
1, B
n
2, and B
n
3 are the partitioned subsets of B
n.IfG is an acyclic graph with order n, then, by Lemmas 1 and 2, the following result holds.Theorem 6.
Let G be an acyclic graph with order n. Then(15)
16
n
-
30
≤
H
M
G
≤
n
2
n
-
1
,where the lower bound is achieved if and only if G
≅
P
n and the upper bound is achieved if and only if G
≅
S
n.Theorem 7.
LetG be a unicyclic graph with n vertices. Then(16)
H
M
C
n
≤
H
M
G
≤
H
M
S
n
1
,where the lower bound is achieved if and only if G
≅
C
n and the upper bound is achieved if and only if G
≅
S
n
1.Proof.
Being a unicyclic graphG contains a unique cycle C
l. By Lemma 3, we can obtain the graph K in which the length of the cycle is three and its H
M is increased strictly and then, by using Lemma 5, we can get the uniquely maximum graph S
n
1 with respect to H
M (Figure 6). By using Lemmas 1 and 4, we find that the minimum graph is C
n.Figure 6
Some graphs.Theorem 8.
LetG be a bicyclic graph with n vertices. Then (17)
16
n
+
70
≤
H
M
G
≤
n
3
-
n
2
+
8
n
+
56
,where the lower bound is achieved if and only if G
∈
{
P
n
k
,
l
,
m
:
l
≥
3
}
∪
{
C
n
(
r
,
l
,
t
)
:
l
≥
3
} and the upper bound is achieved if and only if G
≅
S
n
2.Proof.
By simple calculation, one can obtainH
M
(
S
n
2
)
=
n
3
-
5
n
2
+
16
n
+
4. So, we show that if G
≇
S
n
2, then H
M
(
G
)
<
H
M
(
S
n
2
).
Case  1 (G
Contains
K
4
-
e
as Its Brace). As G contains K
4
-
e as its brace, by using Lemmas 2 and 5, we can obtain a new bicyclic graph G
1 whose H
M is more than that of G (see Figure 6). Clearly, H
M
(
G
1
)
<
n
3
-
5
n
2
+
16
n
+
4.
Case  2 (K
4
-
e
Is Not the Brace of
G). Though G does not contain the subgraph K
4
-
e, by Lemma 3, maybe there is a bicyclic graph having brace K
4
-
e whose H
M is greater than G. So we have two subcases.
Subcase 2.1 (C
n
(
3,2
,
m
)
Is the Brace of
G). By Lemma 3, Subcase 2.1 is converted to Case 1.
Subcase 2.2 (S
n
(
3,2
,
m
)
Is Not the Brace of
G). By Lemmas 2, 3, and 5, we get a new bicyclic graph G
2 (Figure 6) whose H
M is more than that of G. It is easy to verify that H
M
(
G
2
)
<
n
3
-
5
n
2
+
16
n
+
4.
Now we obtain the lower bound of bicyclic graphs with respect toH
M. From Lemmas 1, 2, and 4, we find that the extremal graph of the minimum H
M in bicyclic graphs must be element from the set {
P
n
k
,
l
,
m
,
C
n
(
p
,
q
)
,
C
n
(
r
,
l
,
t
)
}.
Clearly,H
M
(
P
n
k
,
l
,
m
)
=
16
n
+
70, H
M
(
C
n
(
p
,
q
)
)
=
16
n
+
96, and H
M
(
C
n
(
r
,
l
,
t
)
)
=
16
n
+
70.
So, we check the lower bound and equality holds if and only ifG
∈
{
P
n
k
,
l
,
m
:
l
≥
3
}
∪
{
C
n
(
r
,
l
,
t
)
:
l
≥
3
}.



---

*Source: 6079450-2017-02-01.xml*