Abstract. For a (molecular) graph, the first and second Zagreb indices (
M
_{1}
and
M
_{2}
) are two wellknown topological indices, first introduced in 1972 by Gutman and Trinajstić. The first Zagreb index
M
_{1}
is equal to the sum of the squares of the degrees of the vertices, and the second Zagreb index
M
_{2}
is equal to the sum of the products of the degrees of pairs of adjacent vertices. Let
with
n
_{1}
≤
n
_{2}
,
n
_{1}
+
n
_{2}
=
n
and
p
<
n
_{1}
be the set of bipartite graphs obtained by deleting
p
edges from complete bipartite graph
K
_{n1,n2}
. In this paper, we determine sharp upper and lower bounds on Zagreb indices of graphs from
and characterize the corresponding extremal graphs at which the upper and lower bounds on Zagreb indices are attained. As a corollary, we determine the extremal graph from
with respect to Zagreb coindices. Moreover a problem has been proposed on the first and second Zagreb indices.
AMS Mathematics Subject Classification : 05C07, 05C35, 05C90.
1. Introduction
We only consider finite, undirected and simple graphs throughout this paper. Let
G
be a graph with vertex set
V
(
G
) and edge set
E
(
G
). For any vertex
v
∈
V
(
G
), we denote by
N_{G}
(
v
) the set of its neighbors in
G
. The
degree
of
v
∈
V
(
G
), denoted by
d_{G}
(
v
), is the cardinality of
N_{G}
(
v
), i.e., the number of vertices in
G
adjacent to
v
. For a subset
W
of
V
(
G
), let
G

W
be the subgraph of
G
obtained by deleting the vertices of
W
and the edges incident with them. Similarly, for a subset
E′
of
E
(
G
), we denote by
G

E′
the subgraph of
G
obtained by deleting the edges of
E′
. If
W
= {
v
} and
E′
= {
xy
}, the subgraphs
G

W
and
G

E′
will be written as
G

v
and
G

xy
for short, respectively.
K
_{n1,n2}
is a complete bipartite graph of order
n
=
n
_{1}
+
n
_{2}
and two bipartite sets
V
_{1}
and
V
_{2}
with 
V_{i}
 =
n_{i}
for
i
= 1, 2. Other undefined notations and terminology on the graph theory can be found in
[4]
.
A graphical invariant is a number related to a graph which is a structural invariant, in other words, it is a fixed number under graph automorphisms. In chemical graph theory, these invariants are also known as the topological indices. Two of the oldest graph invariants are the wellknown Zagreb indices first introduced in
[17]
where Gutman and Trinajsti´c examined the dependence of total
π
electron energy on molecular structure and elaborated in
[18]
. For a (molecular) graph
G
, the first Zagreb index
M
_{1}
(
G
) and the second Zagreb index
M
_{2}
(
G
) are, respectively, defined as follows:
Another wellknown version of first Zagreb index is in the following:
These two classical topological indices reflect the extent of branching of the molecular carbonatom skeleton
[3
,
22
,
25]
. The main properties of
M
_{1}
and
M
_{2}
were summarized in
[5
,
7
–
9
,
14
–
16
,
20
,
24
,
26
,
28]
. In particular, Deng
[9]
gave a unified approach to determine extremal values of Zagreb indices for trees, unicyclic, and bicyclic graphs, respectively. For some newest applications of Zagreb indices of graphs, please see
[6
,
13
,
14
,
19
,
23]
. In recent years, some novel variants of ordinary Zagreb indices have been introduced and studied, such as Zagreb coindices
[1
,
2
,
10]
, multiplicative Zagreb indices
[12
,
24
,
30]
, multiplicative sum Zagreb index
[11
,
27]
and multiplicative Zagreb coindices
[29]
. Especially the first and second Zagreb coindices of graph
G
are defined
[1
,
10]
in what follows:
Hereafter we always assume that
n
_{1}
,
n
_{2}
,
p
are three positive integers such that
n
_{1}
≤
n
_{2}
,
n
_{1}
+
n
_{2}
=
n
and
p
<
n
_{1}
. We denote by
the set of bipartite graphs obtained by deleting
p
edges from the complete bipartite graph
K
_{n1,n2}
. In this paper we present sharp upper and lower bounds on the Zagreb indices of graphs from
and characterize the extremal graphs at which the upper or lower bounds are attained. As a corollary, we also determine the extremal graph from
with respect to Zagreb coindices. Finally an open problem is proposed on the Zagreb indices.
2. Preliminaries
In this section we list or prove some lemmas as preliminaries, which will be further used .
Lemma 2.1
(
[1
,
2]
). Let
G
be a connected graph of order
n
and with
m
edges.
Then we have

(1)= 2m(n 1) M1(G);

(2)= 2m2M2(G) .
Lemma 2.2.
Let
G
be a connected graph with
e
=
uv
∈
E
(
G
) and
G′
=
G

uv
.
Then we have
M
_{1}
(
G′
) =
M
_{1}
(
G
)  2  2(
d_{G′}
(
u
) +
d_{G′}
(
v
)).
Proof
. By the definition of first Zagreb index, we have
which completes the proof. □
Lemma 2.3.
Let
G
be a connected graph with
uv
∈
E
(
G
) and
N_{G}
(
u
) ╲ {
v
} = {
v
_{1}
,
v
_{2}
,⋯,
v_{α}
} and
N_{G}
(
v
) ╲ {
u
} = {
u
_{1}
,
u
_{2}
,⋯,
u_{β}
}. Suppose that
G′
=
G

uv
.
Then we have
Proof
. From the definition of second Zagreb index, we have
Thus the proof this lemma was completed. □
3. Extremal graphs fromw. r. t. Zagreb indices
In this section we will consider the extremal graphs from
with respect to Zagreb indices. Before presenting the main results, we first introduce some special graphs in
. Let
be a bipartite graph obtained by deleting
p
edges
e
_{1}
,
e
_{2}
,⋯,
e_{p}
from
K
_{n1,n2}
where all
e
_{1}
,
e
_{2}
,⋯,
e_{p}
are pairwise independent. And we denote by
the bipartite graph obtained by deleting
p
edges
e
_{1}
,
e
_{2}
,⋯,
e_{p}
from
K
_{n1,n2}
where
e
_{1}
,
e
_{2}
,⋯,
e_{p}
have a common vertex in the partite set of size
n
_{1}
in it. Similarly,
is a bipartite graph obtained by deleting
p
edges
e
_{1}
,
e
_{2}
,⋯,
e_{p}
from
K
_{n1,n2}
where all
e
_{1}
,
e
_{2}
,⋯,
e_{p}
have a common vertex in the partite set of size
n
_{2}
in it. As three examples,
are shown in
Figure 1
.
The graphs
When
p
= 1, there is only one graph in
, and there is nothing to deal with for our main problem. So in what follows, we always assume that
p
≥ 2. In the following theorem we will determine the extremal graphs from
with respect to the first Zagreb index.
Theorem 3.1.
For any graph
, we have
with left equality holding if and only if
and right equality holding if and only if
for
i
= 1, 2.
Proof
. We prove this result by induction on
p
, i.e., the number of edges deleted from
K
_{n1,n2}
. When
p
= 2, there exist exactly three graphs in the set
, which are just
. From the definition of first Zagreb index, we have
Therefore the results in this theorem hold immediately.
Assume that the results hold for
p
=
k
 1. Now we consider the case when
p
=
k
. For any graph
, there exists a graph
with
uv
∈
E
(
G
^{∗}
) and
G
^{∗}

uv
=
G
. By Lemma 2.2, we have
Now we assume that, at vertices
u
∈
V
_{1}
and
v
∈
V
_{2}
in
G
^{∗}
, there are
k
_{1}
,
k
_{2}
edges, respectively, deleted from
K
_{n1,n2}
. Then we claim that 0 ≤
k
_{1}
+
k
_{2}
≤
k
1 and
d_{G∗}
(
u
)+
d_{G∗}
(
v
) =
n

k
_{1}

k
_{2}
. Considering the facts that
d_{G}
(
u
) =
d_{G∗}
(
u
)1 and
d_{G}
(
v
) =
d_{G∗}
(
v
)  1, we have
Combining these two equalities (3) and (4), we arrive at the following:
Next it suffices to deal with the equality (5). For the left part in (2), by the induction hypothesis and equality (5), we have
The above equality holds if and only if
and
k
_{1}
= 0,
k
_{2}
= 0. Equivalently,
and
ek
=
uv
is independent of any one edge from {
e
_{1}
,
e
_{2}
,⋯,
e
_{k−1}
}. Therefore we have
. Then the proof of the left part in (2) is completed.
Now we turn to the right part of (2). By the induction hypothesis and equality (5), we have
The above equality holds if and only if
for
i
= 1, 2 and
k
_{1}
+
k
_{2}
=
k
1, i.e.,
and
k
_{1}
=
k
1,
k
_{2}
= 0 or
and
k
_{1}
= 0,
k
_{2}
=
k
 1.
Thus we find that, either in
, there are
k
 1 edges deleted from the vertex
u
∈
V
_{1}
of
K
_{n1,n2}
; or in
, there are
k
 1 edges from
v
∈
V
_{2}
of
K
_{n1,n2}
. Therefore, we conclude that
. This completes the proof of this theorem. □
In the theorem below we characterize the extremal graphs from
with respect to the second Zagreb index.
Theorem 3.2.
For any graph
with
n
_{1}
<
n
_{2}
, we have
with left equality holding if and only if
and right equality holding if and only if
.
Proof
. We prove this result by induction on
p
. When
p
= 2, there exist exactly three graphs in the set
, which are just
. From the definition of second Zagreb index, we have
Obviously,
. Thus our results hold as desired.
Now we assume that the results in (6) hold for
p
=
k
1. Then we consider the case when
p
=
k
. For any graph
, there exists a graph
with
u
∈
V
_{1}
,
v
∈
V
_{2}
,
uv
∈
E
(
G
^{∗}
) and
G
^{∗}

uv
=
G
. The structure of
G
^{∗}
is shown in
Fig. 2
where the polygonal lines denote the deleted edges from
K
_{n1,n2}
. Suppose that
N_{G∗}
(
u
) ╲ {
v
} = {
v
_{1}
,
v
_{2}
,⋯,
v_{α}
} ≜
X
_{1}
and
N_{G∗}
(
v
) ╲ {
u
} = {
u
_{1}
,
u
_{2}
,⋯,
u_{β}
} ≜
X
_{4}
. Let
V
_{1}
╲ (
X
_{4}
∪ {
u
}) =
X
_{3}
and
V
_{2}
╲ (
X
_{1}
∪ {
v
}) =
X
_{2}
. By Lemma 2.3, we have
The structure of graph G^{∗}
As introduced in
[8]
, for any vertex
v
in a graph
G
, we denote by
m_{G}
(
v
) the average of the degrees of all vertices adjacent to vertex
v
in
G
. Again we assume that, at vertices
u
∈
V
_{1}
and
v
∈
V
_{2}
in
G
^{∗}
, there are
k
_{1}
;
k
_{2}
edges, respectively, deleted from
K
_{n1,n2}
. Let the number of edges deleted between the two subsets
X
_{1}
,
X
_{3}
in
G
^{∗}
and between the two subsets
X
_{1}
,
X
_{4}
be
x
_{1}
and
y
_{1}
, respectively, the edges deleted between the two subsets
X
_{2}
,
X
_{3}
and between the two subsets
X
_{2}
;
X
_{4}
be
x
_{2}
and
y
_{2}
, respectively. Moreover we have
x
_{1}
+
x
_{2}
+
y
_{1}
+
y
_{2}
=
k
 1 
k
_{1}

k
_{2}
. Then we claim that
From the definition of
m_{G∗}
(
u
), we arrive at:
Similarly, we have
Combining the above two equalities with equality (7), we get
It can be easily checked that the term 2
k
_{1}
n
_{1}
+ 2
k
_{2}
n
_{2}

k
_{1}
k
_{2}
reaches its minimum value 0 when
k
_{1}
=
k
_{2}
= 0. For the left part in (6), from equality (∗) and the induction hypothesis, we have
The above equality holds if and only if
and
k
_{1}
= 0,
k
_{2}
= 0. Moreover, from the statement
k
_{1}
= 0,
k
_{2}
= 0 we can deduce that
ek
=
uv
is independent of any edge of {
e
_{1}
,
e
_{2}
,⋯,
e
_{k−1}
}. Therefore we find that
, which ends the proof of left part in (6).
Now we will turn to the proof for the right part in (6). From the definition of
m_{G}
(
v
) for any vertex
v
in a graph
G
and the structure of
G
^{∗}
, we have
Similarly, we have
Combining the above two inequalities with equality equality (7), we can obtain
Clearly the term 2(
n
_{2}
1)
k
_{2}
+2(
n
_{1}
1)
k
_{1}

k
_{1}
k
_{2}
reaches its maximum value 2(
n
_{2}
1)(
k
 1) when
k
_{1}
= 0 and
k
_{2}
=
k
1. From the induction hypothesis, it follows that
The above two equalities holds if and only if
and
k
_{1}
= 0,
k
_{2}
=
k
 1. That is to say,
G
is obtained by deleting from
one more edge which has one common vertex with that one of {
e
_{1}
,
e
_{2}
,⋯,
e
_{k−1}
} in it. Therefore we claim that
, finishing the proof of right part in (6). Thus we complete the proof of this theorem. □
Note that
if
n
_{1}
=
n
_{2}
. We denote by
this graph when
n
_{1}
=
n
_{2}
. By a similar reasoning as that in the proof of Theorem 3.2, the following corollary can be easily obtained.
Corollary 3.1.
For any graph
, we have
with left equality holding if and only if
and right equality holding if and only if
.
Now we turn to the determination of extremal graphs from
with respect to Zagreb coindices. Based on Lemma 2.1 (1), we have
Moreover the following result can be easily obtained.
Corollary 3.2.
For any graph
, we have
with left equality holding if and only if
for
i
= 1, 2 and right equality holding if and only if
.
In view of Lemma 2.1 (2), we have
Corollary 3.3.
For any graph
, we have
with left equality holding if and only if
and right equality holding if and only if
.
Proof
. From Lemma 2.1 (2), it suffices to find the extremal graphs from
at which the maximal (or minimal, resp.) first and second Zagreb indices are simultaneously attained. Note that, from Theorems 3.1 and 3.2, the first Zagreb index and second Zagreb index of graphs from
with
n
_{1}
<
n
_{2}
reach the maximum only when
. Thus our results follow immediately from Theorems 3.1 and 3.2. □
4. A related problem
In this section we propose a problem related to the extremal graphs with respect to Zagreb indices. Based on the alternative formula (1) of the first Zagreb index and the definition of the second Zagreb index, these two indices have very similar versions. Therefore, from the intuition, we think that, in a given set
G
of connected graphs, the graphs with maximal first Zagreb index are the same as the graphs with maximal second Zagreb index, and vice versa; and the graphs with minimal first Zagreb index are the same as the graphs with minimal second Zagreb index, and vice versa. We say that this set
G
satisfies extremal identical graph property with respect to Zagreb indices (EIG property w. r. t. Zagreb indices for short). Actually, our statement is true for many known results, such as trees, unicyclic graphs, and bicyclic graphs (see
[9]
), and so on. Furthermore, our main result in this paper is also a positive example to our statement given above.
Now we would like to propose an interesting problem related to the EIG property as follows:
Problem 1.
Characterizing the sets Γ of graphs which satisfy EIG property w. r. t. Zagreb indices?
Moreover, it is reasonable to restrict the consideration to the cases when the set Γ contains connected graphs of the same order.
Obviously, from Lemma 2.1, if a set Γ satisfies EIG property w. r. t. Zagreb indices, then it also satisfies EIG w. r. t. Zagreb coindices. Moreover we can also study the EIG property of any set of graphs with respect to other vertexdegreebased topological indices, which may be of interest to us.
BIO
Kexiang Xu received M.Sc. from Southeast University and Ph.D at Nanjing Normal University in China. He is an associate professor of Mathematics in Nanjing University of Aeronautics & Astronautics of China. His research interests include graph theory with its applications.
Department of Mathematics, College of Science, Nanjing University of Aeronautics & Astronautics, Nanjing, Jiangsu 210016, PR China.
email: kexxu1221@126.com
Kechao Tang received M.Sc. from Nanjing University of Aeronautics & Astronautics of China.
Department of Mathematics, College of Science, Nanjing University of Aeronautics & Astronautics, Nanjing, Jiangsu 210016, PR China.
email: tangkechao3@163.com
Hongshuang Liu is a M.Sc. student in Nanjing University of Aeronautics & Astronautics of China.
Department of Mathematics, College of Science, Nanjing University of Aeronautics & Astronautics, Nanjing, Jiangsu 210016, PR China.
email: 992868875@qq.com
Jinlan Wang is a M.Sc. student in Nanjing University of Aeronautics & Astronautics of China.
Department of Mathematics, College of Science, Nanjing University of Aeronautics & Astronautics, Nanjing, Jiangsu 210016, PR China.
email: 774189209@qq.com
Ashrafi A.R.
,
Došlić T.
,
Hamzeh A.
(2011)
Extremal graphs with respect to the Zagreb coindices
MATCH Commun. Math. Comput. Chem.
65
85 
92
Balaba A.T.
,
Motoc I.
,
Bonchev D.
,
Mekenyan O.
(1983)
Topological indices for structure activity corrections
Topics Curr. Chem.
114
21 
55
Bondy J.A.
,
Murty U.S.R.
1976
Graph Theory with Applications
Macmillan Press
New York
Das K.C.
,
Akgünes N.
,
Togan M.
,
Yurttas A.
,
Cangül I.N.
,
Cevik A.S.
On the first Zagreb index and multiplicative Zagreb coindices of graphs
Analele Stiintifice ale Universitatii Ovidius Constanta
in press
Das K.C.
,
Gutman I.
(2004)
Some properties of the second Zagreb index
MATCH Commun. Math. Comput. Chem.
52
103 
112
Deng H.
(2007)
A unified approach to the extremal Zagreb indices for trees, unicyclic graphs and bicyclic graphs
MATCH Commun. Math. Comput. Chem.
57
597 
616
Došlić T.
(2008)
Vertexweighted Wiener polynomials for composite graphs
Ars Math. Contemp.
1
66 
80
Eliasi M.
,
Iranmanesh A.
,
Gutman I.
(2012)
Multiplicative versions of first Zagreb index
MATCH Commun. Math. Comput. Chem.
68
217 
230
Gutman I.
(2011)
Multiplicative Zagreb indices of trees
Bulletin of Society of Mathematicians Banja Luka
18
17 
23
Gutman I.
(2014)
An exceptional property of first Zagreb index
MATCH Commun. Math. Comput. Chem.
72
733 
740
Gutman I.
,
Das K.C.
(2004)
The first Zagreb index 30 years after
MATCH Commun. Math. Comput. Chem.
50
83 
92
Gutman I.
,
Polansky O.E.
1986
Mathematical Concepts in Organic Chemistry
Springer
Berlin
Gutman I.
,
Trinajstić N.
(1972)
Graph theory and molecular orbitals. III. Total πelectron energy of alternant hydrocarbons
Chem. Phys. Lett.
17
535 
538
DOI : 10.1016/00092614(72)850991
Gutman I.
,
Ruščić B.
,
Trinajstić N.
,
Wilcox C.F.
(1975)
Graph theory and molecular orbitals. XII. Acyclic polyenes
J. Chem. Phys.
62
3399 
3405
DOI : 10.1063/1.430994
Lučić B.
,
Nikolić S.
,
Trinajstić N.
2012
Zagreb indices, in: Chemical information and computational challenges in the 21st century, edited by M.V. Putz
Nova Sci. Publ.
New York
261 
275
Nikolić S.
,
Kovačević G.
,
Miličević A.
,
Trinajstić N.
(2003)
The Zagreb indices 30 years after
Croat. Chem. Acta
76
113 
124
Todeschini R.
,
Ballabio D.
,
Consonni V.
2010
Novel molecular descriptors based on functions of new vertex degrees, In: Novel molecular structure descriptors  Theory and applications I. (I. Gutman, B. Furtula, eds.)
Univ. Kragujevac
Kragujevac
73 
100
Todeschini R.
,
Consonni V.
2000
Handbook of Molecular Descriptors
WileyVCH
Weinheim
Todeschini R.
,
Consonni V.
(2009)
Zagreb indices (Mn), in: Molecular descriptors for chemoinformatics
WileyVCH
Weinheim
955 
966
Todeschini R.
,
Consonni V.
(2010)
New local vertex invariants and molecular descriptors based on functions of the vertex degrees
MATCH Commun. Math. Comput. Chem.
64
359 
372
Trinajstić T
1992
Chemical Graph Theory
CRC Press
Raton, FL
Xu K.
,
Das K.C.
(2012)
Trees, unicyclic, and bicyclic graphs extremal with respect to multiplicative sum Zagreb index
Math. Comput. Chem.
68
257 
272
Xu K.
,
Das K.C.
,
Balachandran S.
(2014)
Maximizing the Zagreb indices of (n,m) graphs
MATCH Commun. Math. Comput. Chem.
72
641 
654
Xu K.
,
Das K.C.
,
Tang K.
(2013)
On the multiplicative Zagreb coindex of graphs
Opuscula Math.
33
197 
210
Xu K.
,
Hua H.
(2012)
A unified approach to extremal multiplicative Zagreb indices for trees, unicyclic and bicyclic graphs
MATCH Commun. Math. Comput. Chem.
68
241 
256