Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 6 (2013) 117–125
Some properties of
the Zagreb eccentricity indices
Kinkar Ch. Das ∗
Department of Mathematics, Sungkyunkwan University
Suwon 440-746, Republic of Korea
Dae-Won Lee
Sungkyunkwan University, Suwon 440-746, Republic of Korea
Ante Graovac
Faculty of Science, University of Split, Nikole Tesle 12, HR-21000 Split, Croatia
Received 10 October 2011, accepted 20 January 2012, published online 5 June 2012
Abstract
The concept of Zagreb eccentricity (E1 and E2) indices was introduced in the chemical
graph theory very recently [5, 12]. The first Zagreb eccentricity (E1) and the second Zagreb
eccentricity (E2) indices of a graph G are defined as
E1 = E1(G) =
∑
vi∈V (G)
e2i
and
E2 = E2(G) =
∑
vivj∈E(G)
ei · ej ,
where E(G) is the edge set and ei is the eccentricity of the vertex vi in G. In this paper we
give some lower and upper bounds on the first Zagreb eccentricity and the second Zagreb
eccentricity indices of trees and graphs, and also characterize the extremal graphs.
Keywords: Graph, first Zagreb eccentricity index, second Zagreb eccentricity index, diameter, eccen-
tricity.
Math. Subj. Class.: 05C40, 05C90
∗Corresponding author.
E-mail addresses: kinkardas2003@googlemail.com (Kinkar Ch. Das), haverd2001@gmail.com (Dae-Won
Lee), ante.graovac@irb.hr (Ante Graovac)
Copyright c© 2013 DMFA Slovenije
118 Ars Math. Contemp. 6 (2013) 117–125
1 Introduction
Mathematical chemistry is a branch of theoretical chemistry using mathematical methods
to discuss and predict molecular properties without necessarily referring to quantum me-
chanics [1, 8, 14]. Chemical graph theory is a branch of mathematical chemistry which
applies graph theory in mathematical modeling of chemical phenomena [6]. This theory
has an important effect on the development of the chemical sciences.
Topological indices are numbers associated with chemical structures derived from their
hydrogen-depleted graphs as a tool for compact and effective description of structural for-
mulas which are used to study and predict the structure-property correlations of organic
compounds. Molecular descriptors are playing significant role in chemistry, pharmacol-
ogy, etc. Among them, topological indices have a prominent place [13]. One of the best
known and widely used is the connectivity index, χ , introduced in 1975 by Milan Randić
[11]. The Randić index is one of the most famous molecular descriptors and the paper in
which it is defined is cited more than 1000 times. The first M1, and the second M2, Zagreb
indices (see [2],[3],[4],[7],[9] and the references therein) are defined as:
M1 = M1(G) =
∑
vi∈V (G)
d2i
and
M2 = M2(G) =
∑
vivj∈E(G)
di · dj .
where di is the degree of the vertex vi ∈ V (G) in G.
Let G = (V,E) be a connected simple graph with |V (G)| = n vertices and |E(G)| =
m edges. Also let di be the degree of the vertex vi, i = 1, 2, . . . , n. For vertices vi, vj ∈
V (G), the distance dG(vi, vj) is defined as the length of the shortest path between vi and
vj in G. The eccentricity of a vertex is the maximum distance from it to any other vertex,
ei = max
vj∈V (G)
dG(vi, vj) .
The maximum eccentricity over all vertices of G is called the diameter of G and denoted
by d.
The invariants based on vertex eccentricities attracted some attention in Chmistry. In an
analogy with the first and the second Zagreb indices, M. Ghorbani et al. and D. Vukičević
et al. define the first E1, and the second, E2, Zagreb eccentricity indices by [5, 12]
E1 = E1(G) =
∑
vi∈V (G)
e2i (1.1)
and
E2 = E2(G) =
∑
vivj∈E(G)
ei · ej . (1.2)
where E(G) is the edge set and ei is the eccentricity of the vertex vi in G.
LetG = (V (G), E(G)) . If V (G) is the disjoint union of two nonempty sets V1(G) and
V2(G) such that every vertex in V1(G) has degree r and every vertex in V2(G) has degree
K. Ch. Das, D.-W. Lee and A. Graovac: Some properties of the Zagreb eccentricity indices 119
s, then G is (r, s)-semiregular graph. When r = s , is called a regular graph. As usual,
Ka,b (a + b = n), Pn and K1,n−1 denote respectively the complete bipartite graph, the
path and the star on n vertices. A vertex of a graph is said to be pendent if its neighborhood
contains exactly one vertex. An edge of a graph is said to be pendent if one of its vertices
is a pendent vertex. Now we calculate
E1(Pn) =
{
1
12 (n− 1)(7n
2 − 2n) if n is even
1
12 (n− 1)(7n
2 − 2n− 3) if n is odd.
(1.3)
and
E2(Pn) =
{
1
12 n(7n
2 − 21n+ 20) if n is even
1
12 (n− 1)(7n
2 − 14n+ 3) if n is odd.
(1.4)
Also we have
E1(K1,n−1) = 4n− 3 and E2(K1,n−1) = 2n− 2.
Denote by T̃n, is a tree of order n with maximum degree n − 2. We have E1(T̃n) =
9n− 10, E2(T̃n) = 6n− 8.
In this paper we give some lower and upper bounds on the first Zagreb eccentricity
and the second Zagreb eccentricity indices of trees and graphs, and also characterize the
extremal graphs.
2 Lower and upper bounds on Zagreb eccentricity indices
We now give lower and upper bounds on the Zagreb eccentricity indices of trees.
Theorem 2.1. Let T be a tree with n vertices. Then
(i) E1(K1,n−1) ≤ E1(T ) ≤ E1(Pn) (2.1)
and (ii) E2(K1,n−1) ≤ E2(T ) ≤ E2(Pn). (2.2)
Moreover, the left hand side (right hand side, respectively) equality holds in (2.1) and (2.2)
if and only if G ∼= K1,n−1 (G ∼= Pn, respectively).
Proof. Upper bound: If T is isomorphic to path Pn, then the right hand side equality holds
in (2.1) and (2.2). Otherwise, T  Pn. Let d be the diameter of tree T . Then there exists a
path Pd+1 : v1v2 . . . vd+1 of length d in T . Thus we have the eccentricity of a vertex vi in
tree T ,
ei = max{dG(vi, v1), dG(vi, vd+1)} .
Since T is a tree, both vertices v1 and vd+1 are pendent vertices. Thus we have ei ≤ d for
each vi ∈ V (G). Since T  Pn, let vk (k 6= 1, d+ 1) be a vertex of degree one, adjacent
to vertex vj in T . We transform T into another tree T ∗ by deleting the edge vk vj and
join the vertices vd+1 and vk by an edge. Then the longest path Pd+2 : v1v2 . . . vd+1vk
of length d + 1 in T ∗. Let the vertex eccentricities be e∗1, e
∗
2, . . . , e
∗
n in T
∗. Therefore
we have e∗t = max{d∗G(vt, v1), d∗G(vt, vk)} = max{dG(vt, v1), dG(vt, vd+1) + 1} ≥
max{dG(vt, v1), dG(vt, vd+1)} = et (as d∗G(vt, vk) = dG(vt, vd+1) + 1) for t 6= k
whereas e∗k = d+1 > d ≥ ek (d∗G(vi, vj) is the length of the shortest path between vertices
120 Ars Math. Contemp. 6 (2013) 117–125
vi and vj in T ∗). So we have e∗r e
∗
s ≥ er es for vrvs 6= vkvj , vkvd+1 and e∗k e∗d+1 =
d(d+ 1) > d2 ≥ ek ej . Using above result we get
E1(T
∗)− E1(T ) =
∑
vi∈V (T∗)
e∗2i −
∑
vi∈V (T )
e2i ≥ e∗2k − e2k > 0
and
E2(T
∗)− E2(T ) =
∑
vr vs∈E(T∗)
e∗r e
∗
s −
∑
vr vs∈E(T )
er es ≥ e∗k e∗d+1 − ek ej > 0.
Therefore we have
Ei(T
∗) > Ei(T ), i = 1, 2.
By the above described construction we have increased the value of Ei(T ), i = 1, 2. If
T ∗ is the path, we are done. If not, then we continue the construction as follows. Next we
choose one pendent vertex (6= v1, vk) from T ∗, etc. Repeating the procedure sufficient
number of times, we arrive at a tree in which the maximum degree 2, that is, we arrive at
path Pn.
Lower bound: If T is isomorphic to star K1,n−1, then the left hand side equality holds
in (2.1) and (2.2). If T is isomorphic to T̃n, then the left hand side inequality is strict in
(2.1) and (2.2). Otherwise, T  K1,n−1 , T̃n . Suppose that a path Pd+1 : v1v2 . . . vd+1
of length d in T , where d is the diameter of T . Without loss of generality, we can assume
that d2 ≥ dd (the degree of vertex v2 is greater than or equal to the degree of vertex vd).
Now choose vi to be an arbitrary maximum degree vertex, unless vd has maximum degree,
in which case vi is chosen to be v2. We transform T into another tree T̂ by deleting the
edge vd vd+1 and join the vertices vi and vd+1 by an edge. Let the vertex eccentricities be
ê1, ê2, . . . , ên in tree T̂ . Similarly, as before we obtain êt ≤ et for all t = 1, 2, . . . , n.
Using above we get
E1(T̂ )− E1(T ) =
∑
vi∈V (T̂ )
ê2i −
∑
vi∈V (T )
e2i ≤ 0
and
E2(T̂ )− E2(T ) =
∑
vr vs∈E(T̂ )
êr ês −
∑
vr vs∈E(T )
er es ≤ 0.
Therefore we have
Ei(T̂ ) ≤ Ei(T ), i = 1, 2.
By the above described construction we have non-increased the value of Ei(T ), i =
1, 2. If T̂ is to the tree T̃n , we are done. If not, then we continue the construction as follows.
Next we choose one pendent vertex from longest path in T̂ such that its adjacent vertex is
not maximum degree vertex. Now we delete that pendent edge and join the pendent vertex
to the maximum degree vertex, etc. Repeating the procedure sufficient number of times,
we arrive at a tree in which the maximum degree n − 2, that is, we arrive at tree T̃n. This
completes the proof.
K. Ch. Das, D.-W. Lee and A. Graovac: Some properties of the Zagreb eccentricity indices 121
We now give lower and upper bounds on the Zagreb eccentricity indices of bipartite
graph.
Theorem 2.2. Let G be a connected bipartite graph of order n with bipartition V (G) =
U ∪W , U ∩W = ∅, |U | = p and |W | = q. Then
(i) E1(Kp,q) ≤ E1(G) ≤ E1(Pn) (2.3)
and (ii) E2(Kp,q) ≤ E2(G) ≤ E2(Pn). (2.4)
Moreover, the left hand side (right hand side, respectively) equality holds in (2.3) and (2.4)
if and only if G ∼= Kp,q (G ∼= Pn, respectively).
Proof. If G is isomorphic to a complete bipartite graph Kp,q , then the left hand side
equality holds in (2.3) and (2.4). Otherwise, G  Kp,q . If we add an edge in G,
then each vertex eccentricity will non-increase. Thus we have ei(G + e) ≤ ei(G). Us-
ing this property, one can see easily that E1(G) ≥ E1(Kp,q\{e}) > E1(Kp,q) and
E2(G) ≥ E2(Kp,q\{e}) > E2(Kp,q) , where e is any edge in Kp,q .
Let T be a spanning tree of connected bipartite graph G. Then by the above property,
E1(G) ≤ E1(T ) and E2(G) ≤ E2(T ). Using this result with Theorem 2.1, we get the
right hand side inequality in (2.3) and (2.4). Moreover, the right hand side equality holds
in (2.3) and (2.4) if and only if G ∼= Pn. This completes the proof.
In [10], Hua et al. proved the following result in Theorem 3.1.
Lemma 2.3. Let G be a connected graph with ei = n − di for any vertex vi ∈ V (G). If
G  P4, then ei ≤ 2 for any vertex vi ∈ V (G).
We now give some relation between first Zagreb index and the first Zagreb eccentricity
index of graphs.
Theorem 2.4. Let G be a connected graph of order n with m edges. Then
E1(G) ≤M1(G)− 4mn+ n3, (2.5)
where M1(G) is the first Zagreb index in G. Moreover, the equality holds in (2.5) if and
only if G ∼= P4 or G ∼= Kn or G is isomorphic to a (n− 1, n− 2)-semiregular graph.
Proof. If G ∼= P4, then the equality holds in (2.5). Otherwise, G  P4. Now,
E1(G) =
∑
vi∈V (G)
e2i ≤
∑
vi∈V (G)
(n− di)2 as ei ≤ n− di
= M1(G)− 4mn+ n3 as M1(G) =
∑
vi∈V (G)
d2i ,
∑
vi∈V (G)
di = 2m.
First part of the proof is over.
Now suppose that equality holds in (2.5). Then ei = n − di for all vi ∈ V (G). By
Lemma 2.3, we conclude that ei ≤ 2 for any vertex vi ∈ V (G) as G  P4. Since
ei = n − di for any vertex vi ∈ V (G), we must have di = n − 1 or n − 2 for any vertex
vi ∈ V (G), that is, G ∼= Kn or G is isomorphic to a (n− 1, n− 2)-semiregular graph.
Conversely, one can see easily that (2.5) holds for P4 orKn or (n−1, n−2)-semiregular
graph.
122 Ars Math. Contemp. 6 (2013) 117–125
Remark 2.5. (n−1, n−2)-semiregular graph is obtained by deleting i independent edges
from Kn, 1 ≤ i ≤ bn2 c.
We now give some relation between first Zagreb index, second Zagreb index and the
second Zagreb eccentricity index of graphs.
Theorem 2.6. Let G be a connected graph of order n with m edges. Then
E2(G) ≤M2(G)− nM1(G) +mn2, (2.6)
whereM1(G) is the first Zagreb index,M2(G) is the second Zagreb index inG. Moreover,
the equality holds in (2.6) if and only if G ∼= P4 or G ∼= Kn or G is isomorphic to a
(n− 1, n− 2)-semiregular graph.
Proof. Now,
E2(G) =
∑
vivj∈E(G)
ei · ej
≤
∑
vivj∈E(G)
(n− di)(n− dj) as ei ≤ n− di and ej ≤ n− dj
=
∑
vivj∈E(G)
(
n2 + didj − (di + dj)n
)
= M2(G)− nM1(G) +mn2.
First part of the proof is over. Moreover, one can see easily that the equality holds in (2.6)
if and only ifG ∼= P4 orG ∼= Kn orG is isomorphic to a (n−1, n−2)-semiregular graph,
by the proof of Theorem 2.4.
Figure 1: Graphs G∗ and G∗∗.
Let K12,a−2 be a connected graph of order a obtained from the complete bipartite graph
K2,a−2 with the vertices of degree a− 2 are adjacent. Denote by G∗, is a connected graph
K. Ch. Das, D.-W. Lee and A. Graovac: Some properties of the Zagreb eccentricity indices 123
of order n, obtained from K12,n−2q−2 by attaching two paths Pq+1 to two of its vertices of
degree n − 2q − 1. Let Γ1 be the class of graphs H1 = (V,E) such that H1 is connected
graph of diameter d (d = 2q + 1) with V (G∗) = V (H1) and E(G∗) ⊆ E(H1).
Let K23,a−2 be a connected graph of order a + 1 obtained from the complete bipartite
graph K2,a−2 with the vertices of degree a − 2 are adjacent to a new vertex. Denote by
G∗∗, is a connected graph of order n, obtained from K23,n−2q−1 by attaching two paths
Pq to two of its vertices of degree n − 2q. Let Γ2 be the class of graphs H2 = (V,E)
such that H2 is connected graph of diameter d (d = 2q + 2) with V (G∗) = V (H2) and
E(G∗) ⊆ E(H2).
We now give another lower bound on E1(G) in terms of n, d and also characterize the
extremal graphs.
Theorem 2.7. Let G be a connected graph of order n with diameter d. Then
E1(G) ≥
{
1
12 (3nd
2 + 6nd+ 3n+ 4d3 + 3d2 − 4d− 3) if d+ 1 is even
d
12 (3nd+ 4d
2 + 9d+ 2) if d+ 1 is odd
(2.7)
with equality holding if and only if G ∼= Pn or G ∈ Γ1 or G ∈ Γ2 .
Proof. Since G has diameter d, G contains a path Pd+1: v1 v2 . . . , vd+1. Moreover, n ≥
d+ 1 and ei ≥ dd2e, i = 1 , 2 , . . . , n. If n = d+ 1, then G ∼= Pn and the equality holds in
(2.7). Otherwise, n > d+ 1. By (1.3), we get
d+1∑
i=1
e2i =
{
d
12 (7d
2 + 12d+ 5) if d+ 1 is even
d
12 (7d
2 + 12d+ 2) if d+ 1 is odd.
(2.8)
Since ei ≥
⌈
d
2
⌉
, i = 1 , 2 , . . . , n, using above result, we get
E1(G) =
d+1∑
i=1
e2i +
n∑
i=d+2
e2i
≥
{
d
12 (7d
2 + 12d+ 5) + (n− d− 1)dd2e
2 if d+ 1 is even
d
12 (7d
2 + 12d+ 2) + 14 (n− d− 1)d
2 if d+ 1 is odd,
(2.9)
from which we get the required result (2.7). First part of the proof is over.
Now suppose that equality holds in (2.7) with n > d + 1. From equality in (2.9), we
get
ei =
⌈d
2
⌉
for i = d+ 2 , d+ 3 , . . . , n.
Using above result we conclude that all the vertices vd+2 , vd+3 , . . . , vn−1 and vn are
adjacent to vertices vq and vq+2 (when d = 2q), or vq+1 and vq+2 (when d = 2q + 1).
Hence G ∈ Γ1 or G ∈ Γ2.
Conversely, one can see easily that (2.7) holds for path Pn or graph G, where G ∈ Γ1
or G ∈ Γ2.
124 Ars Math. Contemp. 6 (2013) 117–125
We now give another lower bound on E2(G) in terms of m, d and also characterize the
extremal graphs.
Theorem 2.8. Let G be a connected graph of order n with diameter d. Then
E2(G) ≥
{
1
12 (3md
2 + 6md+ 4d3 − 6d2 − 4d+ 3m+ 6) if d+ 1 is even
d
12 (3md+ 4d
2 − 4) if d+ 1 is odd
(2.10)
with equality holding if and only if G ∼= Pn or G ∈ Γ1 or G ∈ Γ2 .
Proof. By (1.3), we get
∑
vivj∈E(Pd+1)
ei ej =
{
d+1
12 (7d
2 − 7d+ 6) if d+ 1 is even
d
12 (7d
2 − 4) if d+ 1 is odd.
(2.11)
Since ei ≥
⌈
d
2
⌉
, i = 1 , 2 , . . . , n, we have
E2(G) =
∑
vivj∈E(Pd+1)
ei ej +
∑
vivj∈E(G\Pd+1)
ei ej
≥
{
d+1
12 (7d
2 − 7d+ 6) + (m− d)dd2e
2 if d+ 1 is even
d
12 (7d
2 − 4) + 14 (m− d)d
2 if d+ 1 is odd,
from which we get the required result (2.10). Rest of the proof is similar as Theorem
2.7.
Acknowledgement. The authors are grateful to the two anonymous referees for their careful
reading of this paper and strict criticisms, constructive corrections and valuable comments
on this paper, which have considerably improved the presentation of this paper. The first
author’s research is supported by Sungkyunkwan University BK21 Project, BK21 Math
Modeling HRD Div. Sungkyunkwan University, Suwon, Republic of Korea.
References
[1] S. J. Cyvin and I. Gutman, Kekulé Structures in Benzenoid Hydrocarbons, Lecture Notes in
Chemistry, Vol 46, Springer Verlag, Berlin, 1988.
[2] K. C. Das, Maximizing the sum of the squares of the degrees of a graph, Discrete Math. 285
(2004), 57–66.
[3] K. C. Das and I. Gutman, Some Properties of the Second Zagreb Index, MATCH Commun.
Math. Comput. Chem. 52 (2004), 103–112.
[4] K. C. Das, I. Gutman and B. Zhou, New upper bounds on Zagreb indices, J. Math. Chem. 46
(2009), 514–521.
[5] M. Ghorbani and M. A. Hosseinzadeh, A new version of Zagreb indices, Filomat 26 (2012),
93–100.
[6] A. Graovac, I. Gutman and N. Trinajstić, Topological Approach to the Chemistry of Conjugated
Molecules, Springer Verlag, Berlin, 1977.
[7] I. Gutman and K. C. Das, The first Zagreb indices 30 years after, MATCH Commun. Math.
Comput. Chem. 50 (2004), 83–92.
K. Ch. Das, D.-W. Lee and A. Graovac: Some properties of the Zagreb eccentricity indices 125
[8] I. Gutman and O. E. Polansky, Mathematical Concepts in Organic Chemistry, Springer Verlag,
Berlin, 1986.
[9] I. Gutman and N. Trinajstić, Graph theory and molecular orbitals. III. Total π-electron energy
of alternant hydrocarbons, Chem. Phys. Lett. 17 (1972), 535–538.
[10] H. Hua and S. Zhang, Relations between Zagreb coindices and some distance-Based topologi-
cal indices, MATCH Commun. Math. Comput. Chem. 68 (2012), 199–208.
[11] M. Randić, On characterization of molecular branching, J. Am. Chem. Soc. 97 (1975), 6609–
6615.
[12] D. Vukičević and A. Graovac, Note on the comparison of the first and second normalized
Zagreb eccentricity indices, Acta Chim. Slov. 57 (2010), 524–528.
[13] R. Todeschini and V. Consonni, Handbook of Molecular Descriptors, Wiley–VCH, Weinheim,
2000.
[14] N. Trinajstić and I. Gutman, Mathematical chemistry, Croat. Chem. Acta 75 (2002), 329–356.