IMFM
Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia
Preprint series Vol. 48 (2010), 1129
ISSN 2232-2094
VARIABLE ZAGREB INDICES AND KARAMATA'S INEQUALITY
Vesna Andova Mirko Petrusevski
Ljubljana, September 15, 2010
Variable Zagreb indices and Karamata's inequality
Vesna Andova" and Mirko Petrusevski6
io

CO CD
Jh
CD CO
Institute of Mathematics and Physics, Faculty of Electrical Engineering and Information Technologies, Ss. Cyril and Methodius Univ.,
CD
Ruger Boskovik, P. O. Box 574, 1000 Skopje, Macedonia, e-mail: vesna.andova@gmail.com
6Institute of Mathematics and Informatics, Faculty of Mechanical Engineering, Ss. Cyril and Methodius Univ. Ruger Boskovik, PO Box 574, 1000 Skopje, Macedonia e-mail: mirko.petrusevski@gmail.com
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. Generalization of these indices gives first AM1(G) and second AM2(G) variable Zagreb indices. Vukicevic in [13] has given an incomplete proof for the claim: for all simple graphs and
all A £ [0, 1 ], holds aMi(G)/n <A M2(G)/m. Here we present a complete proof using Karamata's inequality.
1 Introduction
The concept of the variable molecular descriptors was proposed as an alternative way of characterizing heteroatoms in molecules, but also to assess the structural differences, such as, for example, the relative role of carbon atoms of acyclic and cyclic parts in alkylcycloalkanes. The idea behind the variable molecular descriptors is that the variables are determined during the regression so that the standard error of estimate for a studied property is as small as possible. Several molecular descriptors, have already been generalized in their variable forms, but here we will only pay attention to Zagreb indices. These indices have been used to study molecular complexity, chirality, ZE-isomerism and hetero-systems. Overall, Zagreb indices exhibit a potential applicability for deriving multi-linear regression models.
Let G = (V,E) be a simple graph with n = \V\ vertices and m = \E\ edges. For v £ V, d(v) is its degree. The first Zagreb index M1(G) and the second Zagreb M2(G) index are among the oldest topological indices [1, 3, 5] defined in 1972 by Gutman and Trinajstic [4] as follows:
Mi(G) = y d(v)2 and M2(G) = ^ d(u)d(v).
vEV	uvEE
Similarly, first and second variable Zagreb indices are defined by
MdG) = ^ d(v)2A and AM2(G)=Y^ dA(u)dA(v),
vEV	uvEE
A	A	A
where A is a real number. For the sake of simplicity, we use AM1 and AM2 instead of AM1(G) and aM2(G), respectively.
a
The Zagreb indices are generally related to the inequality M1(G)/n < M2(G)/m and the question: When does this inequality hold? Similarly to this, many mathematicians analyzed the inequality
10
u
CD
CO
m
CD
Mi(G) < aM2(G)	(1)
when A € [0, 1], and showed that it is true for the following cases: all chemical graphs [13], all trees [12], all unicyclic graphs [6]. For more results on this topic see [7, 9, 10, 14]. Vukicevic [13] also analyzed the inequality (1) and showed that it does not holds for A € [^21, 1]. The case when A € [ 1, ^21 ] is still CD an open problem. In the same paper an incomplete proof of the following theorem is given:
^ Theorem 1.1. For all graphs G and all A € [0, 1 ], holds *M1 jn <* M2/m.
Since we discuss sufficient conditions for (1) to hold, for the sake of simplicity we denote by mi,j the number of edges that connect vertices of degrees i and j in the graph G. Then, as shown in [13]:
KMx/n -* Mi/m	f (i,j)'m2j +	9(i,j, k, l)mijmkl,	(2)
i<j i<j,k<l i.jeN	(i,j) = (k,l)
o
where the functions f and g are defined in the following way:
f (i,j) = i* j * + ~) - i2X-1 - j2*-1,	(3)
ij
CN	g(i,j,k,l) = i* j (1 + 1) + k* l* Q + 1) - i2*-1 - j2*-1 - k2*-1 - l2*-1.	(4)
and
In order to examine whether the inequality (1) holds, one can consider whether *M2/m -* M1/n is non-negative. If f (i,j) < 0 or g(i,j, k,l) < 0 for some integers i,j, k, l, then there is a graph G such that the inequality (1) does not hold. The construction of such graph can be done in the same way as the one for Zagreb indices in [13]. S	The proof of the Theorem 1.1 is based on the following two lemmas:
l-H
Lemma 1.1. Let i and j be different natural numbers and let f (i,j) is defined by (3). Then, f (i,j) > 0 for A € [0,1] and f (i,j) < 0 for A € R\[0,1].
Lemma 1.2. Let i,j,k and j be different natural numbers and let A € [0, 1 ]. Then the function g(i,j,k,l) defined by (4) in non-negative.
Without loss of generality, we may assume that i = max{j, k, l} and that k > l. Now, there are three possible orderings:
(a) i > j > k > l,	(b) i > k > j > l,	(c) i > k > l > j.
m
The cases (a) and (b) are proven in [13], even more for these orderings holds g(i,j, k,l) > 0 for all A € [0,1].
dg(% j k l)
The incompleteness in the proof of Lemma 1.2 is for the third ordering. Namely, -—-— is
di
not non-negative [13] in the case (c).
2 Proof of Theorem 1.1
By the above discussion, one can easily see that the main problem here is determining the sign of g for A £ [0, 2]. In order to do that, we will use some already known results [8].
Lemma 2.1. [Karamata's inequality] Let U C R be an open interval and f : U ^ U be a convex
CD
function. Let ai > a2 > ... > an and bi > 62 > • • • > bn belong to U are such that ai + a2 + ... + ai > bi + b2 + ... + bi for every i £ {1, 2,... ,n} with equality for i = n. Then f (a1) + f (a2) + ... + f (an) >
f (bl) + f (b2) + ... + f (bn).
Since monotonicity of the a's only strengthens the majorizing conditions a1 + a2 + ... + ai > b1 + b2 + ... + bi for every i £ {1, 2,... ,n} with equality for i = n, we have that the same inequality holds without any restrictions on order on the a's.
If in addition U = R and the function f is non-decreasing on U, then the majorizing conditions can be further relaxed from "with equality for i = n". Namely if a1 + a2 + ... + an >b1 + b2 + ... + bn, then we take a'n = b1 + b2 + ... + bn — a1 — a2 — ... — an-1. With a'n instead of an we have that all the needed for Karamata's is satisfied and f (an) > f (a'n), which goes on our hand. These comments explain how the following is derived from Lemma 2.1.
CSI
Lemma 2.2. [Majorizing inequality] Let f : R ^ R be a non-decreasing convex function. Let
ai,a2,... ,an and b1 > b2 > ... > bn be reals such that a1 + a2 + ... + ai > b1 + b2 + ... + bi for every i £ {1, 2, .. ., n}. Then f (ai) + f (02) + ... + f (an) > f (bi) + f (ki) + ... + f (bn).

CO CD
CD CO
A Lemma 2.2 will be are use to prove the following result.
Theorem 2.1. Let a, b,c,d £ R+ and x £ [0, i]. Then
axbx(^ + + cxdx(1 + i) > a2x-i + b2x-i + c2x-i + d2x-i. c d	a b
Proof. Put A = — logt a, B = — logt b, C = — logt c, D = — logt d, for a fixed real t > 1. Then this inequality takes on the form
tA-(C+D)x + tB-(c + D)x + t°-(A+B)x + tD-(A+B)x > t(i-2x)A + t(i_2x)B + t(i_2x)C + t(i_2x)D
_
Put ai = A — (C + D)x, a2 = B — (C + D)x, a3 = C — (A + B)x, a4 = D — (A + B)x and bi = (1 — 2x)A, b2 = (1 — 2x)B, b3 = (1 — 2x)C, b4 = (1 — 2x)D.
CO
Without loss of generality we can take that A > B,C, D and C > D. There are three cases to be considered regarding how B is positioned to C, D:
(1) If B > C, then A > B > C > D. Since x £ [0,1/2], i.e., x, 1 — 2x > 0, it is obvious that bi > b2 > b3 > b4 and ai > ^^ bi, for j = 1, 2, 3, 4. So now the sequences ai: a2, a3, a4 and bi, b2, b3, b4 satisfy the (conditions for the majorizing inequality.
Similarly to case (1) the orderings of a's and b's for the other two cases are: (2) if C > B > D, then A > C > B > D, and ai, a3, a2, a4 and bi, b3, b2, b4;
(3) if D > B, then A > C > D > B, and ai, a3, a4, a2 and bi, b3, b4, b2;
and they satisfy the conditions for the majorizing inequality.	□
Proof. (of the Theorem 1.1)
By Theorem 2.1 we have that the function g(i,j, k, l) is non-negative for any positive integers i,j, k, l and any A £ [0, i]. By Lemma 1.1, the function f (i,j) is also non-negative for A £ [0, 2] C [0,1] . Since f and g are non-negative for A £ [0, 2] we have xM2/m —x Mi/n > 0 i.e., xMi/n <x M2/m. This completes the proof.	□
Acknowledgement. We are very grateful to professor R. Skrekovski for his valuable suggestions.
1—1
References
J-i CD
[1] A. T. Balaban, I. Motoc, D. Bonchev, O. Mekenyan, Topological indices for structure-activity
CD
a
00
correlations, Topics Curr. Chem. 114 (1983) 21-55. [2] G. Caporossi, P. Hansen, Variable neighborhood search for extremal graphs. 1. The Auto-GraphiX
system, Discrete Math. 212 (2000) 29-44. [3] J. Devillers, A. T. Balaban, Topological Indices and Related Descriptors in QSAR and QSPR,
Gordon and Breach, Amsterdam, 1999.
[4]	I. Gutman, N. Trinajstic, Graph theory and molecular orbitals. Total ^—electron energy of alternant hydrocarbons, Chem. Phys. Lett. 17 (1971) 535-538.
o
[5]	I. Gutman, K. C. Das, The first Zagreb index 30 years after, MATCH Commun. Math. Comput. Chem. 50 (2004) 83-92.
[6]	B. Horoldagva, K. C. Das, Comparing variable Zagreb indices for unicyclic graphs, MATCH Commun. Math. Comput. Chem. 62 (2009) 725-730.
[7]	Y. Huang, B. Liu, M. Zhang, On comparing the variable Zagreb indices, MATCH Commun.
Math. Comput. Chem. 63 (2010) 453-460.
[8] Z. Kadelburg, D. Dukic, M. Lukic, I. Matic, Inequalities of Karamata, Schur and Muirhead, and some applications, The Teaching of Mathematics 8 (2005) 31-45.
CO
CO [9] B. Liu, Z. You, A survey on comparing Zagreb indices, in: I. Gutman, B. Furtula (Eds.), Novel
Molecular Structure Descriptors - Theory and Applications I, Univ. Kragujevac, Kragujevac, 2010, pp. 227-239.
[10]	B. Liu, M. Zhang, Y. Huang, Comparing the variable Zagreb indices for graphs, MATCH Commun. Math. Comput. Chem. 63 (2010) 441-451.
[11]	S. Nikolic, G. Kovacevic, A. Milicevic, N. Trinajstic, The Zagreb indices 30 years after, Croat. Chem. Acta 76 (2003) 113-124.
CD CO
[12]	D. Vukicevic, A. Graovac, Comparing variable Zagreb Mi and M2 indices for acyclic molecules, MATCH Commun. Math. Comput. Chem. 60 (2008) 37-44.
• I
[13]	D. Vukicevic, Comparing variable Zagreb indices, MATCH Commun. Math. Comput. Chem. 57
&
(2007) 633-641.
o io
[14] M. Zhang, B. Liu, On comparing variable Zagreb indices for unicyclic graphs, MATCH Commun. Math. Comput. Chem. 63 (2010) 461-468.
u
CD
CD
a
CD CO
0 o
1
CO ^
CO CO
m
CD
$h
CD
m
u
a
CD U