Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 5 (2012) 73–76
A note on Zagreb indices inequality for trees and
unicyclic graphs∗
Vesna Andova
Faculty of Electrical Engineering and Information Technologies
Ss Cyril and Methodius Univ., Ruger Boskovik PO Box 574, 1000 Skopje, Macedonia
Nathann Cohen †
Projet Mascotte, I3S (CNRS, UNSA) and INRIA, 2004 route des Lucioles
BP 93, 06902 Sophia-Antipolis Cedex, France
Riste Škrekovski ‡
Department of Mathematics, University of Ljubljana
Jadranska 21, 1111 Ljubljana, Slovenia
Received 10 September 2010, accepted 8 December 2010, published online 2 November 2011
Abstract
For a simple graph G with n vertices and m edges, the inequality M1(G)n ≤
M2(G)
m ,
where M1(G) and M2(G) are the first and the second Zagreb indices of G, is known as
Zagreb indices inequality. Recently Vukičević and Graovac [12], and Caporossi, Hansen
and Vukičević [3] proved that this inequality holds for trees and unicyclic graphs, respec-
tively. Here, alternative and shorter proofs of these results are presented.
Keywords: First Zagreb index, second Zagreb index.
Math. Subj. Class.: 05C05, 05C07, 05C38, 92E10, 94C15
1 Introduction
The first and second Zagreb indices are among the oldest topological indices, defined in
1972 by Gutman et al. [5], and are given different names in the literature, such as the
Zagreb group indices, the Zagreb group parameters and most often, the Zagreb indices.
∗Partial support by bilateral project BI-FR/09-10-PROTEUS-008.
†Partially supported by the ANR Blanc AGAPE and ANR Blanc International-Taiwan GRATEL.
‡Supported in part by ARRS Research Program P1-0297.
E-mail addresses: vesna.andova@gmail.com (Vesna Andova), nathann.cohen@gmail.com (Nathann
Cohen), skrekovski@gmail.com (Riste Škrekovski)
Copyright c© 2012 DMFA Slovenije
74 Ars Math. Contemp. 5 (2012) 73–76
Since then, they have been used to study molecular complexity, chirality, ZE-isomerism
and hetero-systems (see [1, 4, 8, 10, 14]).
In the following, let G = (V,E) be a simple graph with n = |V | vertices and m = |E|
edges. These indices are defined as
M1(G) =
∑
v∈V
d(v)2 and M2(G) =
∑
uv∈E
d(u)d(v),
where d(u) stands for the degree of vertex u. For the sake of simplicity, we will often use
M1 and M2 instead of M1(G) and M2(G), respectively.
In 2003, an article [9] repopularized Zagreb indices, and since then a lot of work was
done on this topic. For more results concerning Zagreb indices see [7, 13]. Comparing the
values of these indices on the same graph was one very natural aim, which gave, and still
gives, very interesting results. At first the next conjecture was proposed [2]:
Conjecture 1.1. For all simple graphs G,
M1(G)
n
≤ M2(G)
m
(1.1)
and the bound is tight for complete graphs.
If the graph is regular then this bound is tight, but it is also tight if G is a star. This
inequality holds for trees [12], graphs of maximum degree four, i.e. so called chemical
graphs [6] and unicyclic graphs [3], but does not hold in general. See [6, 12, 3, 11] for
various examples of graphs dissatisfying the inequality (1.1).
For a connected graph G, the cyclomatic number is ν(G) = m − n + 1. Thus, every
tree has cyclomatic number 0. A graph whose cyclomatic number is 1 is called unicyclic.
Note that such a graph has precisely one cycle.
In chemistry trees, unicyclic graphs, bicyclic graphs, and so on, are very important
graphs since they represent classes of molecules. Trees are graph representation of acyclic
molecules like alkanes (also known as paraffins). Cycloalkanes are types of alkanes which
have one or more rings of carbon atoms in the chemical structure of their molecules, so
their graphs are unicyclic graphs, bicyclic graphs, etc.
In this paper we present alternative proofs concerning the Zagreb indices inequality for
trees and unicyclic graphs.
2 An alternative proof for trees and unicyclic graphs
As we said before, trees and unicyclic graphs satisfy M1/n ≤ M2/m. Here, these results
are proven in a shorter way.
A star with k edges is called a k-star. A path of length k is called a k-path. Let p3(G) be
the number of 3-paths, p2(G) the number of 2-paths, and C3(G) is the number of 3-cycles
in G. Note that
p3(G) + 3C3(G) =
∑
uv∈E
(d(v)− 1)(d(u)− 1), (2.1)
where uv in the summation is the middle edge of the (d(u)− 1) (d(v)− 1) corresponding
3-paths. Obviously, a 3-path corresponds to a 3-cycle when its endvertices coincide.
V. Andova et al.: A note on Zagreb indices inequality for trees and unicyclic graphs 75
Theorem 2.1. For any tree G 6= K1, it holds
M1
n
≤ M2
m
. Moreover, equality holds if and
only if G is a star.
Proof. If G is a k-star, then M1 = kn and M2 = km, by which we have equality in (1.1).
So assume now that G has at least two internal adjacent vertices u and v and that v is the
only internal neighbor of u. Observe that M1 =
∑
v∈V d(v)
2 = 2(p2(G) +m). We have
M2 =
∑
uv∈E
[
(d(v)− 1)(d(u)− 1) + (d(u) + d(v))− 1
]
= p3(G) +M1 −m. (2.2)
Now, since m = n− 1, we obtain
(n− 1)M1 < nM2
(n− 1)M1 < n [p3(G) +M1 − (n− 1)]
0 < p3(G) +
2
n
(p2(G) + (n− 1))− (n− 1).
Notice that p2(G) ≥ 2 for every tree on at least 4 vertices. Now, we will prove that
p3(G) ≥ n − 3, and this will establish the theorem. Let l1, . . . , lk be the leaves adjacent
to u, and let w 6= u be a neighbor of v. To any vertex x at distance at least 2 from
u we associate the 3-path built from the first three edges of the shortest path from x to
l1. To any leaf li, (i 6= 1), we associate the path from w to li. These 3-paths being all
different, we associated a 3-path to any vertex except three, namely l1, u, v, which ensures
that p3(G) ≥ n− 3.
Theorem 2.2. For any unicyclic graph G, it holds
M1
n
≤ M2
m
. Moreover, equality holds
if and only if G is a cycle.
Proof. Since G is an unicyclic graph, m = n, and so we need to show M1 ≤ M2. If G is
a k-cycle then M1 = 4k = M2, and we have equality in (1.1). So, assume that G is not a
cycle, C = x1x2 · · ·xlx1 is the unique cycle of G and x1 has a neighbor y 6∈ V (C). From
(2.1) and the left equality of (2.2), we have
M2 = p3(G) + 3C3(G) +M1 −m.
It is enough to show that M1 + 1 ≤ M2 which is equivalent to M1 ≤ p3(G) + 3C3(G) +
M1 − n− 1, and hence is equivalent to
n+ 1 ≤ p3(G) + 3C3(G). (2.3)
Now, remove the edge x1x2 from the cycle. Then G− x1x2 is a tree and p3(G− x1x2) ≥
n− 3. Including yx1x2x3 we have at least n− 2 different 3-paths.
If C is a 3-cycle, then it is obvious that (2.3) holds. Now, assume l ≥ 4. Observe
that x1x2x3x4, xlx1x2x3, xl−1xlx1x2 are 3-paths all distinct from the 3-paths described.
Hence, p3(G) ≥ n+ 1. This implies (2.3).
76 Ars Math. Contemp. 5 (2012) 73–76
References
[1] D. Bonchev, N. Trinajstić, Overall Molecular Descriptors, 3, Overall Zagreb Indices,
SAR&QSAR Environ. Res. 12 (2001), 213–236.
[2] G. Caporossi and P. Hansen, Variable Neighborhood search for extremal graphs, 1, The Auto-
GraphiX system, Discrete Math. 212 (2000), 29–44.
[3] G. Caporossi, P. Hansen and D. Vukičević, Comparing Zagreb indices of cyclic graphs, MATCH
Commun. Math. Comput. Chem. 63 (2010), 441–451.
[4] I. Gutman, B. Rušćić, N. Trinajstić and C. F. Wilcox, Jr., Graph Theory and Molecular Orbitals,
XII, Acyclic Polyenes, J. Chem. Phys. 62 (1975), 3399–3405.
[5] I. Gutman and N. Trinajstić, Graph theory and molecular orbitals, Total π−electron energy of
alternant hydrocarbons, Chem. Phys. Lett. 17 (1972), 535–538.
[6] P. Hansen and D. Vukičević, Comparing the Zagreb Indices, Croat. Chem. Acta 80 (2007),
165–168.
[7] B. Liu and Z. You, A survey on comparing Zagreb indices, in: I. Gutman, B. Furtula (eds),
Novel Molecular Structure Descriptors – Theory and Applications I, Univ. Kragujevac, Kragu-
jevac, 2010, 227–239.
[8] A. Miličević, S. Nikolić and N. Trinajstić, On Reformulated Zagreb Indices, Molecular Diver-
sity 8 (2004), 393–399.
[9] S. Nikolić, G. Kovačević, A. Miličević and N. Trinajstić, The Zagreb Indices 30 years after,
Croat. Chem. Acta 76 (2003), 113–124.
[10] S. Nikolić, I. M. Tolić, N. Trinajstić and I. Baučic, On the Zagreb Indices as Complexity In-
dices, Croat. Chem. Acta 73 (2000), 909–921.
[11] L. Sun and S. Wei, Comparing the Zagreb indices for connected bicyclic graphs, MATCH
Commun. Math. Comput. Chem. 62 (2009), 699–714.
[12] D. Vukičević and A. Graovac, Comparing Zagreb M1 and M2 indices for acyclic molecules,
MATCH Commun. Math. Comput. Chem. 57 (2007), 587–590.
[13] D. Vukičević and A. Graovac, Comparing ZagrebM1 andM2 indices: Overview of the results,
manuscript.
[14] D. Vukičević, S. Nikolić and N. Trinajstić, On the Path-Zagreb Matrix, J. Math. Chem. 45
(2009), 538–543.