IMFM Institute of Mathematics, Physics and Mechanics JADRANSKA 19, 1000 LJUBLJANA, SLOVENIA Preprint series Vol. 48 (2010), 1130 ISSN 2232-2094 RELATION BETWEEN RANDIC INDEX AND AVERAGE DISTANCE OF TREES Marek Cygan Michal Pilipczuk Riste Skrekovski Ljubljana, September 17, 2010 Relation between Randic index and average distance of trees^ CD O CO £ CO CO u cu Marek Cygan, Michal Pilipczuk"1" and Riste Skrekovski* a CD Abstract The Randic index R(G) of a graph G is the sum of weights (deg(u) deg(v))-0'5 over all edges uv of G, where deg(v) denotes the degree of a vertex v. We prove that for any tree T with n leaves R(T) > ad(T) + max(0, Jn - 2), where ad(T) is the average distance between vertices of T. As a consequence we resolve the conjecture R(G) > ad(G) given by Fajtlowicz in 1988 for the case when G is a tree. o 1 Introduction In chemical graph theory topological indices belong to the set of molecular descriptors that are calculated based on the molecular graph of a chemical compound. In 1975 Milan Randic [11] introduced a topological connectivity index R(G) of a graph G defined as the sum of weights (deg(u) deg(v))-0 5 over all edges uv of G, i.e., ___ i r(g) = y . 1 =, uvtE(C) Vdeg(u) deg(v) (N where deg(v) is the degree of a vertex v. Randic has shown that there exists a correlation of the Randic index with several physico-chemical properties of alkanes such as boiling points, chromatographic retention times, enthalpies of formation, parameters in the Antoine equation for vapor pressure, surface areas and others. More information about Randic index can be found in a survey [7] by Li and Shi or in a book [8] by Li and Gutman. The Wiener index is a distance-based topological index defined as the sum of distances between all pairs of vertices in a graph and is denoted by W (G). It was the first topological index in chemistry [13], introduced in 1945. Since then, the Wiener index has been used to explain various chemical and physical properties of molecules. However the Wiener index can be cubic in the number of vertices of a graph, hence for the sake of simplicity we use the average distance instead jg ad(G) = W (G)/Q ■ i For a one vertex graph K1 we assume R(Ki) = ad(Ki) = 0. For the last two decades researchers are investigating extremal values and relations between topological indices. In 1988 Fajtlowicz [5] stated the following conjecture based on the computer program Graffiti. *This work was supported by bilateral project BI-POL/10-11-004 and by Slovenian ARRS Research Program P1-0297. a ^Department of Mathematics, Computer Science and Mechanics, University of Warsaw, Warsaw, Poland, CD {cygan@,michal.pilipczuk@students}.mimuw.edu.pl * Department of Mathematics, University of Ljubljana, Jadranska 19, 1111 Ljubljana, Slovenia, skrekovski@gmail.com o Conjecture 1.1. For all connected graphs G, R(G) > ad(G). CD a CD Very recently Li and Shi [9] have proven Conjecture 1.1 when 5(G) > n/5 and n > 15. More recent IN results related to extremal values of the RandiC index can be found in [1, 3, 6, 14, 15]. In order to state the results of this paper let us introduce some notation. By distG(u, v) we denote the length of the shortest path between vertices u and v in a connected graph G. The length maxu,v distG(u, v) is a diameter of a graph G, which we denote by diam(G). In particular for trees the diameter is the length of the longest simple path. A star is a tree where at most one vertex is of degree greater than one. Note that a tree with at most three vertices is a star. Also notice that stars are precisely the trees with diameter at most two. The main result of this paper is the following theorem. CD Theorem 1.2. For any tree T with n vertices and nr leaves the following inequality holds: R(T) > ad(T) + max(0, ^n — 2) ■ 00 Moreover if we consider the limit when n goes to infinity, the inequality is sharp for stars. As a consequence we prove Conjecture 1.1 for the case when G is a tree. o 2 Proof of Theorem 1.2 A vertex of degree one is called a pendant vertex or a leaf. By Tn ni we denote the set of all trees with exactly n nodes and ni pendant vertices. Firstly let us define a special class of trees, which will be frequently used in our paper. For a,b > 1,n > a + b + 2 by DC(n,a,b) wedenotea double comet, which is a tree composed of a path containing n — a — b vertices with a pendant vertices attached to one of the ends of the path and b pendant vertices attached to the other end of the path. Thus, DC(n, a, b) has n vertices and a + b leaves, i.e. DC(n, a, b) e Tn a Figure 1: A double comet DC(n, a, b) for n = 16, a = 5, b = 4. We begin our proof with a lemma proving Theorem 1.2 for stars and paths. Lemma 2.1. Let T e Tn,ni be a tree such that ni < 2 (a path) or ni = n — 1 (a star). Then R(T) > ad(T) + max(0, ^kl — 2) ■ CD Jh nab Proof. If n < 2 then the inequality trivially holds, hence we assume n > 3. If T is a star then by direct calculations we obtain ad(T) =2 — n and R(T) = ^Jnl = Vn — 1, whereas if T is a path then ad(T) = n+i and R(T) = V2 + .In both cases the lemma holds. □ Consequently from now on we assume that T e Tn,ni where 3 < n1 < n — 2, which means that we may use the following result proved by Liu et al. in Theorem 5 from [10]. & Theorem 2.2. Let T e Tn,ni, where 3 < n1 < n — 2. Then £ r(T> > ^ + ^r+a — + . o c^ IN a o 00 o CSI I c^ £ CO CO Corollary 2.3. Using the assumption n — 2 > ni > 3 we obtain: R(T) > m—m + vnr — 0.462 . The flow of the proof is as follows. Firstly we show that each tree can be transformed into a double comet without decreasing the average distance and simultaneously preserving the number of vertices and leaves. Since in Corollary 2.3 we only use n and ni disregarding the actual structure of a tree it is enough to show that for double comets we have n_ni + — 0.462 > ad(T) + max(0, ^Jni — 2). Lemma 2.4. Let T e Tn,ni, where 3 < ni < n — 2. There exists a double comet T' = DC(n, a, b) for some a,b > 1, a + b = ni such that ad(T) < ad(T'). Proof. Let us assume that contrary. Let T e Tn,ni be a non-double-commet tree such that for each double comet T' = DC(n, a, b), where a,b > 1, a + b = ni we have ad(T') < ad(T). Among all such trees from Tn,ni we consider a tree with the largest diameter diam(T). Let d = diam(T) and D = viv2 ... vd be a diameter of the tree T. Since T is neither a star nor a double comet we have d > 5. Moreover, we know that vi, vd are leaves and all neighbours of v2, vd_i outside D are pendants, because otherwise D would not be a diameter. Furthermore, since T is not a double comet there exists a vertex outside the diameter x e D that is a neighbour of some vertex vi for 3 < i < d — 2. Observe that after a removal of the edge xvi the tree T decomposes into exactly two parts. Let us denote by Tx the part containing the vertex x and by TD the other one. Similarly after removal of the edge vi_ivi the tree TD decomposes into two parts TDl ,TD2, where vi_i e V (TDl) and vi e V(TD2). Without loss of generality we may assume, that | V (TDl) | < | V (TD2) |, since otherwise we can reverse the diameter D. Let T' be a tree T with the edge xvi removed and xv2 inserted (as in Fig. 2). We claim ad(T') > ad(T). Observe that distances between vertices within V(TD) and within V(Tx) in both trees T, T' are the same. Now we consider distances between vertices in V (TD) and V (Tx). Let a e V(Td), b e V(Tx). Consider two cases: 00 • a e V(TDl), then distT/(a, b) > distT(a, b) — (i — 2), • a e V(TD2), then distT(a, b) > distT(a, b) + (i — 2). Since |V(Td1 )| < |V(Td2)|, we have W(T') > W(T) and so ad(T') > ad(T). If |V(Tx)| > 1 then diam(T') > diam(T), hence the lemma holds for T' because diam(T') is larger. Which means that there exists a double comet T'' = DC(n, a, b), where a + b = ni, such that ad(T'') > ad(T') > ad(T), a contradiction. Thus we know that |V (Tx)| = 1. However we can continue in this manner moving pendant neighbours of vertices vi for 3 < i < d — 2 ending up with a double comet, thus completing the proof. □ Obviously, the biggest value of ad(DC(n, a, b)), where a + b = ni, is obtained when a, b are as close as possible to ni/2, i.e. a = |_ ni J and b = [ n2L ]. These bounds are also observed in [4, 12] (see Theorem 31 in the survey [2]) but as the papers [4, 12] may not be easy to access and as our proof is short, for the sake of completness we decide to include it. ■ i Lemma 2.5. Let T e Tn,k be a double comet DC(n, a, b) for a,b > 1, where 3 < a + b = ni < n — 2. Then n — n i -i + VnT — 0.462 > ad(T) + max(0, ^nl — 2). 2 Proof. Firstly we calculate the average distance for the double comet T: CD (n)ad(T) = W (T) = ab(n — ni + 1) + 2^) +2 (2) + (a + b)(n — ni )(n — ni + 1)/2 + — ^ + 1 IN u CD vi V2 /\/\/\/\/\/\/ / \ / \ / \ / \ / \ / W Vi V2 Vi Vd CD a CD CO o CO 0 o 1 CO ^ CO CO Figure 2: Ilustration of the transformation used in the proof of Lemma 2.4. where ab(n — ni + 1) + 2(2) + 2(2) comes from distances between leaves, (a + b)(n — ni)(n — ni + 1)/2 is the sum of distances between leaves and inner vertices and (n—31+i) is the sum of distances between inner vertices. Using following inequalities: 2ab + 2 a2 + 2 2b < (a + b)2 = ni 2 ni ab < -1 ~ 4 n — ni + 1 3 < (n — nl)3 6 we obtain ad(T)fn\ 0. We multiply the expression by 4, put x,y instead of ni,n — ni and use the previously obtained inequality for ad(T) ( 41 n ) (^^ + Vni — 0.462 — max(0, Vn" — 2) — ad(T)) 2(x + y)(x + y — 1)(| + min(Vx — 0.462,1.538)) — 4ad(T) Q 2(x2 + y2 + 2xy — x — y) min(Vx — 0.462,1.538) + y3/3 — 3xy — y2 — 3x2 > Now we consider two cases. Either ni = x = 3 or ni = x > 4. When x = 3 from the above expression we obtain: 2(9 + y2 + 6y — 3 — y) min(V3 — 0.462,1.538) + y3/3 — 9y — y2 — 27 > 2.5(y2 + 5y + 6)+ y3/3 — y2 — 9y — 27 = y3/3 + 1.5y2 + 3.5y — 12 . & Using the assumption ni < n — 2 which is equivalent to y > 2 we obtain y3/3 + 1.5y2 + 3.5y — 12 > 11/3 > 0. Now we assume that x > 4, hence min(^/x — 0.462,1.538) > 1.5. Since x, y > 2 then xy > x + y, and so we have: a CD CO o CO £ CO CO 2(x2 + y2 + 2xy — x — y)1.5 + y3/3 — 3xy — y2 — 3x2 = y3/3 + 2y2 + 3xy — 3(x + y) > 0 , what ends the proof of the lemma. □ In Lemma 2.1 we prove Theorem 1.2 for paths and stars whereas by Lemmas 2.4 and 2.5 together with Corollary 2.3 we obtain the inequality for all other trees, thus completing the proof of Theorem 1.2. o References [1] M. Aouchiche, P. Hansen, M. Zheng, Variable neighborhood search for extremal graphs 18: conjectures and results about Randic index, MATCH Commun. Math. Comput. Chem. 56 (2007) 541550. [2] A. Dobrynin, R. Entringer, I. Gutman, Wiener Index of Trees: Theory and Applications, Acta Ap-plicandae Mathematicae 66 (3)(2001) 211-249. [3] Z. Du, B. Zhou, N. Trinajstic, On Randic Indices of Chemical Trees and Chemical Unicyclic Graphs, MATCH Commun. Math. Comput. Chem. 62 (1)(2009) 131-142. [4] R. Entringer, Bounds for the average distance-inverse degree product in trees, In: Y. Alavi, D. Lick and A. Schwenk (Eds), Combinatorics, Graph Theory, and Algorithms, New Issues Press, Kalamazoo, (1999) 335-352. [5] S. Fajtlowicz, On conjectures of Graffiti, Discrete Math. 72 (1988) 113-118. [6] J. Gao, M. Lu, On the Randic index of unicyclic graphs, MATCH Commun. Math. Comput. Chem. 53(2005)377-384. HH [7] X. Li, Y. Shi, A survey on the Randic index, MATCH Commun. Math. Comput. Chem. 59 (1)(2008) 127-156. • Sh [8] X. Li, I. Gutman, Mathematical Aspects of Randic-Type Molecular Structure Descriptors, Mathematical Chemistry Monographs No.1, Kragujevac, 2006. [9] X. Li, Y. Shi, Randic index, diameter and average distance, MATCH Commun. Math. Comput. Chem. 64 (2)(2010) 425-431. [10] H. Liu, M. Liu, F. Tian, Trees of extremal connectivity index, Discrete Applied Math. 154 (2006) 106-119. Jh CU [11] M. Randic, On characterization of molecular branching, J. Amer. Chem. Soc. 97 (1975) 66096615. o [12] R. Shi, The average distance of trees, Systems Sci. Math. Sci. 6 (1993) 18-24. [13] H. Wiener, Correlation of Heats of Isomerization and Differences in Heats of Vaporization of Isomers among the Paraffin Hydrocarbons, J. Amer. Chem. Soc. 69 (1947) 2636-2638. [14] L. Zhang, M. Lu, F. Tian, Maximum Randic: index on trees with kpendent vertices, J. Math. Chem. 41(2007) 161-171. & [15] M. Zhang, B. Liu, On a Conjecture about the Randic Index and Diameter, MATCH Commun. Math. Comput. Chem. 64 (2)(2010) 433-442. 0 o 1 00 £ CO CO CO CD Jh CD CO u a CD U