Scientific paper
Note on the Comparison of the First and Second Normalized Zagreb Eccentricity Indices
Damir Vuki~evi}1* and Ante Graovac2
1 Department of Mathematics, University of Split, Nikole Tesle 12, HR-21000 Split, Croatia
2 Faculty of Science, University of Split, Nikole Tesle 12, HR-21000 Split, Croatia and the R. Boskovic Institute,
P.O.B. 180, HR-10002 Zagreb, Croatia
* Corresponding author: E-mail: vukicevi@pmfst.hr
Received: 01-02-2010
This paper is dedicated to Professor Milan Randi} on the occasion of his 80th birthday
Abstract
The conjecture x dG(u)2 / n(G) < X dG(u)dG(v) / m(G) that compares normalized Zagreb indices attracted recently
ue V(G)	uveE(G)
a lot of attention1-9. In this paper we analyze analogous statement in which degree dG(u) of vertex u is replaced by its eccentricity £G(u) in which way we define novel first and second Zagreb eccentricity indices. We show that x £G(u)2 /
ue V(G)
n(G) > x eG(u)eG(v) / m(G) holds for all acyclic and unicyclic graphs and that neither this nor the opposite inequality
uveE(G)
holds for all bicyclic graphs.
Keywords: Eccentricity; normalized molecular descriptor; acyclic graphs; unicyclic graphs; bicyclic graphs;
1. Introduction
The Randic index10 is one of the most famous molecular descriptors and the paper in which it is defined is cited more than 1000 times. This is one of the very few papers that made chemical graph theory and mathematical chemistry flourish. It is defined by
Z(G)= I -r==,
where E(G) is set of edges of G and d(x) = dG(x) is degree of vertex x in G. Obviously,
x{G)= E Kdvy for A = -1/2.
irreE(G)
Already in this paper, author proposed observing exponents different from -1/2. Taking X = 1, one obtains the very famous the second Zagreb index11.
The first and the second Zagreb indices are among the oldest and best known molecular descriptors and it has been shown that they have ability to predict many physi-cochemical properties of chemical compounds (pa-pers12-14 and references within). Molecular descriptors are
graph-theoretical invariants used to predict properties of chemical compounds and they have found many applications out of which one of the most important is in the rational drug design. Namely many physical and chemical properties are strongly correlated with molecular structure and then QSPR models allow predictions which molecules (out of the many theoretically obtained molecules) may be of interest.
The first M1, and second M2, Zagreb indices are defined as:
M2=M2{G)= X dG{u)-dG{v).
meEiC)
(1)
where V(G) is the set of vertices of graph G. Let us denote by n = n (G) the number of vertices of G and by m = m (G) the number of its edges. Recently, the system Auto-GraphX [13,14] (software for making conjuctures created by G. Caporossi and P. Hansen) proposed the following conjecture:
Conjecture 1. For all simple connected graphs, it
holds:
M](G)/n(G)<M2(G)/m(G),
(2)
This conjecture has been disproved1, but it has been proved that it holds for all graphs with maximum degree at most four1, for acyclic graphs2, for unicyclic graphs3'4 and it has been shown that it does not hold for bicyclic graphs4. A crucial role in most of these proofs played the quantity mij = m^ (G) which denotes the number of bonds connecting vertices of degrees i and j. These quantities have been recently extensively studied17-25.
The degree of a vertex is a natural invariant assigned to a vertex. Another very natural invariant is eccentricity eG(u) of a vertex u, namely the maximum distance from u to other vertices, i.e. eG(u) = max{dG(u,v) : ve V(G)}, where dG(u,v) is the distance between vertices u and v. For instance, in kenograph (graph in which hydrogen atoms are neglected) of benzene all vertices have eccentricity 3. In octane eccenticites are (in order of the ap-periance of atoms) 7, 6, 5, 4, 4, 5, 6 and 7.
The invariants based on vertex eccentricities attracted some attention in chemistry12,26. In an analogy with the first and the second Zagreb indices, we define now the first, E1, and second, E2, Zagreb eccentricity indices by
=£,(g) = X £c 00" and

(3)

In the present paper, we study whether and in which cases the normalized versions of these novel indices Ex and E2 satisfy an equation comparable to equation (2). Namely, we want to compare
El(G)/n(G) and E2(G)/m(G) In this paper we show that El(G)/n{G)^E2{G)/m(G)
(4)
(5)
holds for all acyclic and unicyclic graphs. At the end of this paper, we present two bicyclic graphs such that inequality (5) holds for one of them, while another one satisfies just the opposite inequality. In such a way it is shown that for general graphs the inequality (5) is not always valid. The same is true for its opposite inequality.
with its most distant vertex is called eccentric. It is well known that:
1)	if tree has only one center, then each eccentric path passes through this vertex;
2)	if tree has two centers, then each eccentric path passes through the edge connecting these two centers.
Let us prove:
Theorem 2. Let G be a simple connected acyclic graph (tree). Then,
E^G)/n(G)> E2(G)/m(G).
Proof: Let us distinguish two cases:
CASE 1: G has one center c.
Let 0: E(G) ^ V(G) \ {c} be the function which maps edge uv to one of its terminal vertices (u or v) which is more distant from the center c. Note that this function is a bijection. It holds:
w«i'\{c}
"("-I)
irtJ'Vfe}
n(n-1)
>0.
CASE 2: G has two centers c1 and c2. Let %: E(G) \ c1c2 ^ V(G) \ {c1c2} be the function that maps edge uv to one of its terminal vertices which is more distant to c1 and c2. It holds:
»("-i)
This proves the Theorem.
->o.
2. Acyclic graphs
The center of the tree is a vertex with the minimal eccentricity. It is well known that tree has either one center or two adjacent centers. The path connecting a vertex
3. Unicyclic Graphs
Let us start with the following Lemmas: Lemma 3. Let n > 2 and let x0, x1, ... xn be positive
integers such that \xt - xi+l\ < 1 for each i = 0, ... n - 1 and x0 = xn. Then,
it-l	rc-l
Tix<2 - Z^,. •
Proof: Suppose to the contrary and let N be the smallest number such that there are positive integers y0,
yv ... yN such thai y - y+i\ < 1 for each i = 0, ..., N - 1, ^o = yN and e y2 < e yiyi+1. Suppose that N > 3, because otherwise contradiction simply follows. Note that there is no j e {0, ..., N - 1} such that y = yj+1, because otherwise let n
= N-1 and x0 = yo, ... xj = yj, xj+1 = yj+2, xN-1 = yN 2nd then it holds:
n-\ JV-1	JV-L	n-l
Zv=Z->		- y j«2=Zw« »
1=0 /=0	/-0	/=0
which is in contradiction with minimality of N. Let yj = max {y0, ..., yN_x}. Distinguish two cases:
CASE 1: j #0.
Note that yj-t = yj+1 = yj - 1. Let n = N - 1 and x0 = y0,
xj-i=y-v xj=yj+i' xj+i=yj+2' .... xn-i=yN. We have:
which is in contradiction with minimality of n.
CASE 2: j = 0.
Completely analogously as Case 1.
In all cases the contradiction is obtained and Lemma 3 is proved. ■
Lemma 4. Let G be any graph and let u and v be two adjacent vertices in G. Then. |eG(u) - eG(v)| < 1.
Proof: Just note that for each vertex w e V(G). it holds \iG(u,w) - dG(v,w)| < 1. ■
Let G be unicyclic graph and let us denote by C = C(G) its unique cycle. Let G' be a graph obtained by deletion of all edges in E(C). Note that components of G' are trees such that each of them has exactly one vertex in C. A tree with its vertex in C being x we denote by Tx. Let us denote by X = X(G) the set of all vertices in C that correspond to components that are not just a single vertex.
Let us prove:
Theorem 5. Let G be a unicyclic graph. Then.
Proof: Note that n(G) = m(G) for unicyclic graphs, hence we need to prove that
Z ecX«i- Z %
iieI'(G)	xve£(Gt)
i.e. that
Z £c{uf - Z £g(mK(v)
ief(C)	uvsA'jC)
Z M«)2- Z
>0.
Note that
Z £o(4~ Z ic(«)ic(v)ä0
ec(c)
e£(C)
follows from Lemmas 3 and 4. Hence, it is sufficient to prove that
for each x e X. Let us fix one x e X. Let y be one of the furthest vertices from x in G. If y <£ Tx, then let Tx' be a tree obtained from Tx by adding pendant path of length d(x,y) to vertex x. Otherwise, let Tx' = Tx. Let rx be the set of vertices with the smallest eG in Tx. Let us distinguish two cases:
CASE 1: x e T.
Let $x : E(Tx) ^ V(Tx) \ {x} be the function that maps edge uv to one of its terminal vertices that is more distant from x. Note that this function is a bijection. It holds:
CASE 2: x £ rx.
rx is the center of Tx and hence it consists of either one or two vertices (none of which is x). Let us distinguish two subcases:
SUBCASE 2.1: T = {c}.
Let l be a leaf on the maximum distance from x and let Px be a path from x to l. This path passes through c, because it is an eccentric path in Tx. Let d(x,c) = p + 1 and d(c,l) = q. Note that q >p + 1.
Let 0x': E(Tx) \ E(Px) ^ V(Tx) \ V(Px) be the function that maps edge uv to one of its terminal vertices which is
more distant from c (or equivalently from x). Note that this function is a bijection. It holds:
-¿(M^OM^'-O
SUBCASE 2.2: Tx = {c1(c2>.
Let l be a leaf on the maximum distance from x and let Px be a path from x to l. Since, this is eccentric path in Tx, then it passes through c1c2. Without loss of generality we may assume that c1 is closer to x and that c2 is closer to l. Let d(x,c 2) = q + 1 and let d(x,c 2) = q. Note that q > p + 1.
Let $x": E(Tx) \ E(Px) ^ V(Tx) \ V(Px) be the function that maps edge uv to one of its terminal vertices that is more distant from c1 (or equivalently form x or c2). Note that this function is a bijection. It holds:
p
i=0
All the cases are exhausted and the Theorem 2 is proved. ■
4. Bicyclic graphs
Let Gx be a bicyclic graph with 2x + 2 vertices presented in Fig. 1:
Figure 1. Graph Gx.
It can be easily calculated that: X £Gtiu)-£G, {v)/b*(G.c);
ifve£(G,)
Hence,
■ (C2 ) + ' ) + ' ~ 0"H• (ci K/ (C2 ) =

In such a way it is shown that for general graphs the inequality (5) is not always valid. The same is true for its opposite inequality.
5. Conclusions
In this paper, we have shown that x eG(u)2 / n(G) > e £G(u)eG(v) / m(G) holds for all acyctic(Giand unicyclic uvgrG^hs and that neither this nor the opposite inequality holds for all bicyclic graphs. We propose the further study of this inequality as an open problem.
6. Acknowledgment
This work is supported by the Ministry of Science, Education and Sports of the Republic of Croatia through grants nos. 177-0000000-0884 (D.V. & A.G.), 0370000000-2779 (D.V.), and 098-0982929-2940 (A.G.).
7. References
1.	P. Hansen, D. Vukicevic, Croat. Chem. Acta. 2007, 80, 165168.
2.	D. Vukicevic, A. Graovac, MATCH Commun. Math. Comput. Chem. 2008, 60, 37-44.
3.	B. Horoldagva, K. C. Das, MATCH Commun. Math. Comput. Chem. 2009, 62, 725-730.
4.	D. Vukicevic, Comparing Zagreb indices, talk on the meeting of International Academy of Mathematical Chemistry, Dubrovnik 2007.
5.	B. Liu, On a Conjecture about Comparing Zagreb Indices, in: I. Gutman, B. Furtula, (Eds), Recent Results in the Theory of Randic Index, Univ. Kragujevac, Kragujevac 2008, pp. 205-209.
6.	A. Ilic, D. Stevanovic, MATCH Commun. Math. Comput. Chem. 2009, 62, 681-687.
7.	L. Sun, T. Chen, Discrete Appl. Math. 2009, 157, 1650-1654.
8.	D. Vukicevic, MATCH Commun. Math. Comput. Chem. 2007, 57, 633-641.
9.	D. Vukicevic, A. Graovac, MATCH Commun. Math. Com-put. Chem. 2007, 57, 587-590.
10.	M. Randic, J. Am. Chem. Soc, 97 (1975) 6609-6615.
11.	I. Gutman, B. Ruščic, N. Trinajstic, and C. F. J. Wilcox Jr, Chem. Phys, 62 (1975) 3399-3405.
12.	I. Gutman, K. C. Das, MATCH Commun. Math. Comput. Chem. 2004, 50, 83-92.
13.	S. Nikolic, G. Kovacevic, A. Milicevic, N. Trinajstic, Croat. Chem. Acta. 2003, 76, 113-124.
14.	R. Todeschini, V. Consonni, Handbook of Molecular Descriptors, Wiley-VCH, Weinheim, 2000.
15.	G. Caporossi, P. Hansen, Discrete Math. 2000, 212, 29-44.
16.	M. Aouchiche, J. M. Bonnefoy, A. Fidahoussen, G. Caporossi, P. Hansen, P.L. Hiesse, J. Lacheré, A. Monhait, Variable neighborhood search for extremal graphs. 14. The Auto-GraphiX 2 system, in: L. Liberti, N. Maculan, (Eds.), Global Optimization: From Theory to Implementation, Springer, Berlin, 2005, pp. 281-310.
17.	G. Caporossi, I. Gutman, P. Hansen, Comput. Chem, 1999, 23, 469-477.
18.	M. Fischermann, A. Hoffman, D. Rautenbach, L. Volkmann, Discrete Appl. Mat, 2003, 128, 375-385.
19.	G. Caporossi, I. Gutman, P. Hansen, Lj. Pavlovic, Comput. Biol. Chem, 2003, 27, 85-90.
20.	D. Vukicevic, A. Graovac, Croat. Chem. Acta, 2004, 77, 481-490.
21.	D. Vukicevic, A. Graovac, Croat. Chem. Acta, 2004, 77, 501-508.
22.	D. Vukicevic, N. Trinajstic, MATCH Commun. Math. Com-put. Chem, 2005, 53, 111-138.
23.	D. Veljan, D. Vukicevic, J. Math. Chem, 2006, 40, 155-178.
24.	D. Vukicevic, Glasnik Matematicki, 2009, 44, 259-266.
25.	G. Caporossi, P. Hansen, and D. Vukicevic, Edge Realizabi-lity of connected simple graphs, Optimization Letters, submitted.
26.	V. Konstantinova, J. Chem. Inf. Comput.Sci. 1996, 36, 54-57.
Povzetek
Trditev s dG(u)2 / n(G) < s dG(u)dG(v) / m(G), ki primerja normalizirane Zagrebške indekse, je nedavno pritegnila
ue V(G)	uveE(G)
precej pozornosti.1-9 V tem članku analiziramo analogno trditev, v kateri stopnjo vozlišča u, dG(u), zamenjamo z njegovo ekscentričnostjo eG(u). Po tej poti definiramo nov prvi in drugi Zagrebški indeks ekscentričnosti. Pokazali bomo, da neenakost s £G(u)2 / n(G) > s £G(u)£G(v) / m(G) drži za vse aciklične in eno-ciklične grafe in da niti ta, niti nas-
ue V(G)	uveE(G)
protna neenakost ne držita za vse dvo-ciklične grafe.