IMFM Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia Preprint series Vol. 49 (2011), 1156 ISSN 2232-2094 ON A VARIATION OF RANDIC INDEX Vesna Andova Martin Knor Primož Potočnik Riste Skrekovski Ljubljana, August 10, 2011 m M 3 u cu On a variation of Randic index V. Andova* M. Knorj P. Potocnikf R. Skrekovski§ August 9, 2011 Abstract 1 Introduction vO lO Randic index, R, also known as the connectivity or branching index, is an important topological index in chemistry. In order to attack some conjectures concerning Randic index, Dvorak et al. [5] introduced a modification of this index, denoted by R'. In this paper we present some of the basic properties of R'. We determine graphs with minimal and maximal values of R', as well as graphs with minimal and maximal values of R' among the trees and unicyclic graphs. We also show that if G is a triangle-free graph on n vertices with minimum degree S, then R'(G) > S. Moreover, equality holds only for the complete bipartite graph . I Molecular descriptors are invariants that are calculated from the topological information contained in the structure of the graph of a molecule [14]. Topological information of a molecule comprises the position and sometimes the type of the atoms defined in relation to CM the bonds that connect them. Such topological descriptors correlate with certain compound properties and activities. In studying branching properties of alkanes, several numbering schemes for the edges of the associated hydrogen-suppressed graph were proposed based on the degrees of the endvertices of an edge. In 1975 Randic [13] introduced the topological connectivity index R(G) of a graph G defined as the sum of weights (degG(u)degG(v))_ 2 over all edges uv of G, i.e., R(G) = £ 1 uv£E(G) y/degG(u)degG(v), where degG(v) is the degree of the vertex v in G. Originally this index was named "branching index" or "molecular connectivity index" and it has been proved to be suitable for measuring the extent of branching of the carbon-atom skeleton of saturated hydrocarbons. Nowadays Jh CD 'Institute of Mathematics and Physics, Faculty of Electrical Engineering and Information Technolo- CO gies, Ss Cyril and Methodius Univ., Ruger Boskovik bb, P. O. Box 574, 1000 Skopje, Macedonia, vesna.andova@gmail.com. ^Department of Mathematics, Faculty of Civil Engineering, Slovak University of Technology, Radlinskeho 11, 813 68, Bratislava, Slovakia, knor@math.sk. * Faculty of Mathematics and Physics, University of Ljubljana, and Institute of Mathematics, Physics and Mechanics, Jadranska 21, 1111 Ljubljana, Slovenia, primoz.potocnik@fmf.uni-lj.si. ^Faculty of Mathematics and Physics, University of Ljubljana, and Institute of Mathematics, Physics and Mechanics, Jadranska 21, 1111 Ljubljana, Slovenia, skrekovski@gmail.com. this parameter is known as Randic index. Later, in 1998 Bollobas and Erdös [1] generalized this index by replacing — 2 with any real number a to obtain the general Randic index Ra. o CM I CO CD $H CD Thus, Ra(G)= Y, (degG(u)degG(v))a uveE(G) 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, en- thalpies of formation, parameters in the Antoine equation for vapor pressure, Kovats constants, calculated surface areas and others [9, 13]. According to Caprossi and Hansen [2], Randic index together with its generalizations is certainly the molecular-graph-based structure-descriptor, that found many applications in organic chemistry, medicinal chemistry, and pharmacology, and therefore is an interesting topic in graph theory. For more results concerning Randic index see [11]. Recently Dvorak et al. [5] have shown that for every connected graph G we have R(G) > rad(G)/2, where rad(G) is the radius of G. The main idea in their work was introducing a new index R'(G) defined as: fi 1 R (G) SG) max{degG (u), degG (v) } ' uvGE(G) Although no application of the index R' in chemistry is known so far, still this index turns out to be very useful, especially from mathematical point of view, as it is much easier to follow during graph modifications than Randic index. Using this index, Cygan et al. [4] proved that for any connected graph G of maximum degree four which is not a path with even number of vertices, R(G) > rad(G). As a consequence, they resolve the conjecture R(G) > rad(G) — 1 given by Fajtlowicz [6] in 1988 for the case when G is a chemical graph. They actually showed CM that for all connected chemical graphs G the inequality R'(G) > rad(G) — 2 holds. Motivated by some already known results concerning Randic index, in this paper we present some basic properties of the newly introduced index R'. We show that for every graph G on n vertices, R'(G) is at least 1 but no more than n, and these bounds are attained by stars and regular graphs, respectively. Then we determine graphs with minimal and maximal value of R' among all trees and unicyclic graphs. It turns out that the same trees and unicyclic graphs attain minimal (maximal) values of R' and Randic index. In the last part we prove that if G is a triangle-free graph on n vertices with minimum degree 5, then R'(G) > 5. Equality holds only for complete bipartite graph . Now, we define terms and symbols used in the sequel. Let G = (V(G),E(G)) be a simple graph on n = \ V(G)| vertices and m = |E(G)| edges. The degree of a vertex v in G is denoted by degG(v), and the set of neighbors of v in G is denoted by NG(v). By 5(G) and A(G) we denote the minimum and maximum degree in G, respectively. The set of vertices of degree a in G is denoted by Va(G). A diameter of connected graph G, diam(G), is the maximum distance between vertices of G, i.e., diam(G) = max{dG(u, v) \ u,v £ V(G)}. Let v be a vertex of a graph G. The graph G — v is obtained from G when v and all edges incident to v are removed. By G~ we denote a graph obtained from G by adding one edge joining two vertices of degree 1. If G is a tree then G^ is a unicyclic graph. Observe that G^ is not determined uniquely. A subdivision of an edge is a replacement of this edge by a path of positive length. Of course, all internal vertices of this new path have degrees 2. A graph H is a subdivision of G if H arises by subdivision of some of the edges of G. A star with n vertices, Sn, is called an n-star. Similarly, a path Pn and a cycle Cn are called an n-path and an n-cycle, respectively, if they have n vertices. 2 Basic properties of R' Here we present some basic properties of R'. From the definition of R', it is obvious that if G is not connected, then R'(G) is the sum of the R' indices of its components. Therefore, in what follows we consider only connected graphs. We start with upper and lower bounds for R' in general graphs. Proposition 2.1. For every graph G on n vertices the inequality R'(G) < R(G) < n holds. Moreover, R'(G) = n if and only if G is a regular graph. Proof. From the definitions of R and R' it is obvious that R(G) > R'(G). It is known that among all connected graphs of order n, regular graphs attain the maximum Randic index [3]. Since R'(G) = R(G) = n if G is a regular graph, we obtain the result. □ o o CM i CO To obtain a lower bound for R' we need the following lemma. Recall that all our graphs are connected. Lemma 2.2. Let G be a graph on at least 2 vertices. Further, let S be an independent set of vertices of G, such that for every u,v £ V(G), where v £ S and uv £ E(G), we have degG(u) < degG(v). Denote by ES those edges xy of G for which neither x nor y is in S. Then R'(G) = \S\ + y -t--^-. max{degG(u), degG(v)J CM S Proof. Let v £ S. Denote by Ev the edges of G incident to v. Then {Ev : v £ S} U {ES} is a partition of E(G). Since every edge of Ev contributes to R'(G) precisely 1/degG(v) and since there are degG(v) edges in Ev, we have ( ) ' ( ma^de^iu! Hp^(vU ) + veS xuveEv max{degG(u),degG(v)^ max{degG(u),degG(v)} \s\ + y 1 uveEs max{degG(u), degG(v)} □ Since the contribution of every edge to R' is positive, Lemma 2.2 can be used to bound R' r . Jh Corollary 2.3. Let G be a graph on at least 2 vertices. Further, let S be an independent set of vertices of G, such that for every u,v £ V(G), where v £ S and uv £ E(G), we have degG(u) < degG(v). Then R'(G) > \S\. We can now obtain the following consequence of Corollary 2.3 and Lemma 2.2. & Corollary 2.4. For every graph G on at least 2 vertices we have R'(G) > 1. Moreover, R'(G) = 1 if and only if G is the star Sn. Proof. Let S consist of a single vertex v of maximum degree in G. Then degG(u) < degG(v) for every uv £ E(G), so that R'(G) > 1 for every graph G on at least 2 vertices by Corollary 2.3. On the other hand, if R'(G) = 1 then all the edges of G must be incident to v, by Lemma 2.2. Hence, if R'(G) = 1 then G is a star. □ i—l By using different methods, Bollobas and Erdos [1], and Pavlovic and Gutman [12] independently showed that among all graphs of order n without isolated vertices, the star Sn attains the minimum Randic index as well, and R(Sn) = Vn — 1. Lemma 2.2 gives an interesting bound for trees with small diameter. Corollary 2.5. Let T be a tree of order n, n > 3, and let v be an internal vertex of T with minimal degree. Denote k = degT(v) and denote by l the number of leaves adjacent to v. Then, R'(G) > k — l + k. Proof. Denote T0 = T—v. Then T0 is a disconnected graph and k — l components of T0 have at least one edge. Denote these components by T1,T2,..., Tk-l. As v is the internal vertex with minimal degree, each Ti, 1 < i < k — l, contains a vertex ui such that degT(u) > degT(x) for every vertex x such that xui £ E(T). As uiuj £ E(T) for 1 < i < j < k — l, the set S = {ui,u2,... ,uk-i} satisfies the assumptions of Lemma 2.2. Since the pendant edges incident with v contain none of u1, u2,..., uk-i, we have R'(T) > (k—1) +1 by Lemma 2.2. □ Observe that all trees in Table 1 attain the bound of Corollary 2.5. Next lemma shows that removing a vertex of degree 1 decreases the value of R'. i CM Lemma 2.6. Let G1 be a graph on at least 3 vertices and let v £ V(G1) such that degGl (v) = 1. Denote G2 = G1 — v. Let u be the unique neighbor of v. Denote a = degGl (u) and denote by l the number of neighbors of u whose degree is at least a. Then CO CM CM l R'(Gi) — R'(G2)= ( 1). a(a — 1) Proof. When v is removed, the degree of u decreases by 1 while the vertices of V(G1) \ {u, v} have the same degree in G2 as in G1. Hence, only edges incident with u affect the difference R'(G1) — R'(G2). Let x1,x2,... ,xl be neighbors of u such that degGl(xi) > degGl(u) for i = 1, 2,... ,l. Then R' (G1) — R'(G2) = — 1( ) + d 1( ) + • • • + d 1( )) a VdegGi (^1) degGi (x2) degGi (xl)J fa — l — 1 ( 11 1 —--^--1---1-----1-- V a — 1 VdegG2 (x1) degG2 (x2) degG2 (xl) a — l a — l — 1 l a a — 1 a(a — 1)' which completes the proof. □ • 1 Jh Using the previous result we describe a situation when a leaf is removed from his position and it is attached to another leaf. Next lemma shows that in this case the value of R' is not decreasing. Lemma 2.7. Let a graph Gi have at least four vertices, let v be a vertex of degree 1 in Gi and let u be its neighbor. Denote a = degGl (u) and denote by l the number of neighbors of u whose degree is at least a. Denote G2 = Gi — v. Let w be a vertex of degree 1 in G2 and let G3 be a graph obtained by attaching a pendant edge to w. Then i—l R'(Gs) — R'(Gi) = 1 — ( l 1) > 0. 2 a(a — 1) $ Proof. By Lemma 2.6, R'(Gi) — R'(G2) = ^¿ij• Now we calculate R'(Gs) — R'(G2). Since G2 has at least 3 vertices, there is a unique neighbor of w whose degree is at least 2 in G3. Since the degree of w is 2 in G3, by Lemma 2.6 we have R'(G3) — R'(G2) = 2• Hence, R'(Gs) — R'(Gi) = (r'(Gs) — R'(G2)) — (R'(GI) — R'G)) = 1 — > 2 — a > 0, as a > l > 0 and a > 2. □ 3 Trees and unicyclic graphs i CM 00 CM CM Here we determine trees and unicyclic graphs attaining the smallest (the greatest) values of R. We start with their definition. By Dk,n we denote a double star on n vertices, i.e., a tree having one vertex of degree k, one vertex of degree n — k and n — 2 leaves. By Sk,n we denote a tree of order n which is a subdivision of the star Sk. Hence, Sk, n has one vertex of degree k — 1, every other vertex has degree either 1 or 2. Observe that the graph of double star D3, 6 resembles the letter H. Therefore by Hk n we denote a subdivision of D3,6 on n vertices in which the vertices of degree 3 are joined by a path of length k By BSn we denote a unicyclic graph obtained from a triangle by identifying centers of two stars, Sk and Sn-k-i, with two different vertices of the triangle. Observe that B^n has one CO vertex of degree k + 1, one vertex of degree n — k, one vertex of degree 2 and n — 3 vertices of degree 1. Note that Bfn = Bfn for l = n — k — 1. Analogously, by Bp (and Dp) we denote a unicyclic graph on n vertices obtained from a triangle (a quadrangle) by identifying endvertices of two paths with two different vertices of the triangle (with two nonadjacent vertices of the quadrangle). Then both Bp and Dp have 2 vertices of degree 3, 2 vertices of degree 1 and n — 4 vertices of degree 2. Finally, by Yp we denote a unicyclic graph on n vertices obtained from a triangle by identifying endvertices of three distinct paths with three distinct vertices of the triangle. Then Yp has 3 vertices of degree 3, 3 vertices of degree 1 and n — 6 vertices of degree 2. First we discuss trees on n vertices, n > 2, with smallest value of R'. By Corollary 2.4, the star Sn attains the minimal value of R' and R'(Sn) = 1. For the next smallest values of R we use the following proposition. Proposition 3.1. Let T be a tree on at least 2 vertices. Then, R'(T) > 2 if and only if diam(T) > 3. Moreover, if diam(T) = 3 then R'(T) = 2 — a, where a is the smallest degree in T which is (greater than 1. a Proof. We distinguish three cases. Suppose first that diam(T) < 2. Since T has at least 2 vertices, T is a star Sn and R'(Sn) = 1 by Corollary 2.4. CO M < vD lO 0 Ö o 1 CO ^ CO CO CO CD Jh CD CO $H a CD Jh CU Suppose now that diam(T) = 3. Then T has exactly 2 vertices, say u and v, whose degree is greater than 1, and moreover, these two vertices are adjacent. All the other vertices have degree 1. Hence, T is a double star. Assume that degT(u) > degT(v). Then r'(t ) = i uxeE(T ) degT (u) + £ i vyEE(T )\{vu} degT(v) = 2 - i degT(v) Finally, suppose that diam(T) > 4. Then there are vertices x and y such that dG(x, y) = 4. Therefore, there is a path P : xviv2vsy of length 4 in T. Applying Lemma 2.6, we can remove vertices from T, one by one, until we obtain the path P. By Lemma 2.6, R'(T) > R'(P). Since for S = {vi, vs} we get R'(P) = 2 by Lemma 2.2, we have R'(T) > 2. n By Proposition 3.1, if T is not a star and R'(T) < 2, then diam(T) = 3. Hence, the trees with smallest values of R' and the corresponding values of R' are given in Table 1, where k = \n/2\. We remark that the next value of R'(T) is 2 but there are more types of trees attaining this value. G Sn Sn-1,n D3,n D4,n D5,n Dk,n R'(G) 1 3/2 5/3 7/4 9/5 (2k - 1)/k Table 1. Trees with smallest values of R'. For unicyclic graphs we use the following proposition. Proposition 3.2. Let C be the unique cycle in a unicyclic graph G. If the length of C is at least 4, or if G has a vertex at distance at least 2 to C, or if the length of C is 3 and all the vertices of C have degrees at least 3 in G, then R'(G) > 2. On the other hand, R'(S^ ) = § and R'(B S ) = 2 fc+1 i) ~ k+1 > where 2 < k R'(Gi) > • • • > R'(Gr). By Proposition 2.1, if C has length c then R'(Gr) = R'(C) = §. Hence, if c > 4 then R'(Gr) > 2 and consequently R'(G) > 2. In what follows suppose that C has length 3. Then R'(Gr) = R'(C) = §. If G = S^ then all vertices of degree 1 are adjacent to one vertex, say u, of C. Since there is a unique edge which is not incident with u in G and both endvertices of this edge have degrees 2, we have R'(S^) = | by Lemma 2.2. If there is a vertex at distance at least 2 from C, then there is Gt, 0 < t < r, such that to obtain Gt+i we remove a vertex adjacent to a vertex of degree 2. Then R'(Gt) — R'(Gt+i) = i, by Lemma 2.6, and hence R'(G) > 2. Thus, in the following we may assume that all the vertices of V(G) — V(C) have degree 1 and are adjacent to a vertex of C. Suppose that there are exactly two vertices of C, say u and v, whose degrees are greater than 2. Assume that degG (u) > degG(v). Then all the edges of G are incident to u or v, so that R'(G) = ^ E 1 " 1 y ^ N degT(u) uxeE(T) v ' vyEE(T )\{vu} degT(v) =2 degT(v) i.e., R'(B%/n) = f+r with 2 < k < n — k — 1. Observe that in any case R'(G) > 2 — 3. CO M < vD lO Finally, suppose that all the vertices of C have degree at least 3 in G. Then there is Gt+1 such that Gt+1 = B^n for some k. By Lemma 2.6 we have R'(Gt) — R'(Gt+1) = 3. As R'(Gt+i) > 2 — 1, we have R'(G) > 2. □ By Proposition 3.2, in Table 2 we have unicyclic graphs with greatest values of R' and the corresponding values of R'. In the last column k = |(n — 1)/2J. We remark that the next value of R' in a unicyclic graph is 2, but as it can be seen from the proof of Proposition 3.2, there are more types of unicyclic graphs G for which R'(G) = 2. Gao and Lu [8] show that among all unicyclic graphs, S^ also attains minimum for Randic index. G Sn B2,n B3,n B s R'(G) 3/2 5/3 7/4 9/5 11/6 (2k + 1)/(k + 1) Table 2. Unicyclic graphs with smallest values of R'. 0 Ö o 1 CO £ CO CO CO CD $H CD CO u a CD U Now we turn our attention to trees with greatest values of R'. Caporossi et al. [3] prove that among all trees on n vertices, the path Pn attains the maximum value of Randic index. In the same paper they prove that S4,n attains the second maximum value of Randic index. Next proposition shows that the same holds for R' as well. G Pn S4,n Hl,n R'(G) (n - 1)/2 (n - 2)/2 (n - 2)/2 - 1/3 (n - 3)/2 Table 3. Trees with greatest values of R'. Proposition 3.3. The trees listed in Table 3 attain the greatest values of R'. All the remaining trees on n vertices have R' smaller than (n — 3)/2. Proof. Let T = T0 be any tree on n vertices different from the trees present in Table 3, and let P0 be a longest path in T0. Take a leaf u0 which is not on P0, remove it from To, join it by an edge to an endvertex of P0 and denote the resulting graph by T1. Repeating this process we get a sequence of trees T0,T1,..., Tr, such that Tr = Pn. By Lemma 2.7, we have R'(T0) < R'(T1) < ■ ■ ■ < R'(Tr). Moreover, by Lemma 2.7 again, if u is adjacent to a vertex of degree 2 in Ti, 0 < i 2, if vi and v2 are nonadjacent, and S5,n. Let t be the greatest value, 0 < t < s, such that ut is adjacent to a vertex of degree at least 3. Denote by vt the unique neighbor of ut in Tt. As R'(H1,n) = n— — 3 and R'(Hkn) = R'(S5in) = — if k > 2, to finish the proof it suffices to show that R'(Tt) < n-3. Since R'(Tt) < R'(Ts), we can assume that Ts = H1 ,n. If the degree of vt is 4, then R'(Ts) — R'(Tt) = R'(Tt+i) — R'(Tt) = 1, by Lemma 2.7, as no neighbor of vt has degree at least 4 in Tt. Thus, R'(Tt) = (— 1) — 1 < n—3. On the other hand if the degree of vt is 3, then R'(TS) — R'(Tt) > 2 — £, by Lemma 2.7, as at most one neighbor of vt has degree at least 3 in Tt. Thus, R'(Tt) < (n—2 — 3) — 1 + 1 < n—3. □ lO Finally, we consider unicyclic graphs with the greatest values of R'. Caparossi et al. [3] also considered the maximum values of Randic index in the class of unicyclic graphs. They show that among all unicyclic graphs of order n the cycle Cn attains the maximum value and 2 < a CD U cu attains the second maximum value of Randic index. We show that the same holds for G Cn S4 ,n H+ RP H1,n Bn h + s + nF yf R'(G) n/2 (n - 1)/2 (n - 1)/2 - 1/3 (n - 2)/2 Table 4. Unicyclic graphs with greatest values of R'. Proposition 3.4. The unicyclic graphs listed in Table 4 attain the greatest values of R'. All the remaining unicyclic graphs on n vertices have R' smaller than (n — 2)/2. Proof. First observe that if R'(G) = £ then R'(GJ) = £ +1. Therefore R'(Cn) = R'(Pf) = f, R'(Stn) = , R'(Htn) = n-1 — 1 and R'(Hln) = R'(St,n) = if k > 2. As BP has 5 edges incident to vertices of degree 3 while every other vertex is incident to a vertex of degree 2, we have R'(Bp) = | + n. Finally, as both Dp and Yp have 6 edges incident to vertices of degree 3 while every other vertex is incident to a vertex of degree 2, we have R'(Dp) = R'(Y,nP) = 3 + 6. Let G be a unicyclic graph with the unique cycle C. If the length of C is n then G = Cn. Hence, suppose that the length of C is smaller than n. Denote G0 = G and denote by F° a longest path in Go. Then at least one vertex of F0 has degree 1. Let u0 be a vertex of degree 1 which is not on F0. Remove u0 from G0, join it by an edge to an endvertex of P0 which degree is 1 and denote the resulting graph by G1. Repeating this process we get a sequence of unicyclic graphs G0,G1 ,...,Gr with R'(G0) < R'(G1) < ■■■ < R'(Gr), by Lemma 2.7. Observe that Gr consists of the cycle C with a path, attached to C by an endvertex. Analogously as in the proof of Proposition 3.3 we get R'(Gr—1) < R'(Gr). As Gr = Sjn, among unicyclic graphs with cycles of length strictly smaller than n, SJ n has the greatest value of R'. Now consider Gr—1 and denote by vr—1 the unique vertex adjacent to ur—1. If degGr_x (vr—1) is 4, then Gr—1 = Sjn. Now, suppose that degGr_ 1 (vr—1) = 3. Denote by w the other vertex of degree 3 in Gr—1. We distinguish six cases: vr-\ G V(C), dar_i(w,vr-{) = 1 and C = C3: Then Gr-\ = B • vr—1 e V(C), dGr-1 (w,vr-\) = 1 and C = C3: Then Gr—1 = CM • vr-1 e V(C), dGr-1 (w,vr—1) = 2 and C = C4: Then Gr-1 = Dp. CD • vr-1 e V(C) and either dGr-1 (w,vr-1) > 2 or dGr-1 (w,vr-1) = 2 and C = C4: Then Gr-i = Hin for k > 2. C0 • vr-1 e V(C) and dGr-1 (w,vr-1) = 1: Then Gr-1 = H{"n. M • vr-1 e V(C) and dGr_ 1 (w,vr—1) > 1: Then Gr-1 = H^n for k > 2. vO lO Observe that in any case, Gr— 1 is a graph presented in Table 4. Let t be the greatest value, 0 < t < r — 1, such that ut is adjacent to a vertex, say vt, of degree at least 3. Then R'(Gm) = R'(Gt+2) = • • • = R'(Gr—1) and R'(Gt) < R'Gt+i) by Lemma 2.7. To finish the proof we have to find all Gt with R'(Gt) > n——2 in the case when Gr—1 = H{n or Gr—1 = BP, see Table 4. If degGi (vt) = 4 then R'(Gr—1) — R'(Gt) = R'(Gt+1) — R'(Gt) = 1 as there is no vertex in Gt — vt of degree at least 4. Hence, assume that degG, (vt) = 3. Observe that R'(Gt+1) = — 3 and so n—2 — R'(Gt+1) = 6. Hence, if m CD 1 u CD R'(Gt) > n—2, then 1 — a(al—1) < 6 by Lemma 2.7, where a = degGi(vt) and l is the number of neighbors of vt whose degree is at least 3. This gives l = 2 and R'(Gt+1) — R'(Gt) = |. Therefore Gt+1 = Bp and vt is a vertex of C = C3. Consequently, Gt = Yp, which finishes the proof. □ CM 4 Triangle-free graphs Favaron et al. [7], showed that for any triangle-free graph G with m edges, we have R(G) > \[m. Later Li and Liu [10] proved the following: For any triangle-free graph G of order n and minimum degree 5(G) = k > 1, we have R(G) > a/k(n — k). Equality holds if and only if G = Kkn—k. In this section we show that if a graph G on n vertices has maximum degree at most n — 5(G), then the lower bound for R'(G) is 5(G). Consequently, this gives a bound for triangle-free graphs, and this bound is attained by Kk,n—k. Theorem 4.1. Let G be a simple graph on n vertices with 5(G) = k, k > 1, A(G) < n — k, n > 2k, and such that when satisfying all these conditions, R'(G) is as small as possible. Then R' (G) = k and G = Kk,n—k. In order to prove Theorem 4.1, we extend it to graphs with multiple edges. Hence, suppose that G is a graph on n vertices, possibly with multiple edges, with 5(G) = k, k > 1, A(G) < n — k, n > 2k, not necessarily connected, and such that when satisfying all these conditions, the parameter R'(G) is as small as possible. In the following two lemmas we prove that G is a bipartite graph with bipartition (Vn-k(G),Vk(G)). Observe that since R'(Kk,n-k) = k, we already have R'(G) < k. & Lemma 4.2. If |V(G)\<\Vn-k(G)| + \Vk(G)| + 1, then |V(G)| = \Vn-k(G)| + \Vk(G)| and G is a bipartite graph with bipartition (Vn-k(G),Vk(G)). Proof. First assume that \V(G)| = \Vn-k(G)| + \Vk(G)| + 1. Let v be the vertex such that k < degG(v) < n — k. Then v has neighbors only in Vk(G) and Vn-k(G). Denote l = degG(v) and a = \NG(v) n Vk(G)\. Then \NG(v) n Vn-k(G)\ = l — a. Further, denote a = \ Vk(G)\ and b = \Vn-k(G)\. Finally, assume that there are s and t edges whose both endvertices are in Vn-k(G) and Vk(G), respectively. Counting the number of edges in two ways, namely through their endvertices of "higher", respectively "smaller" degree gives CO \E (G) \ = b(n — k) — s + a + t = ak — t + (l — a) + s. M Since a + b = n — 1, after dividing by n we obtain , , 2a l — k 2s 2t b = k--+-+---. n n n n Now we evaluate R'(G). There are b(n — k) — s edges with an endvertex in Vn-k(G), a edges connecting v with a vertex of Vk(G) and t edges connecting two vertices of Vk(G). Hence, i—l . b(n — k) — s + a + t R (G)= n-k + J + k and after substituting for b the previous expression we obtain , n - 2l l - k n - 2k n - 2k R'(G) = k + a-— +-+ s—-— +1-—. nl n n(n - k) nk Since n - 2k > 0, we have sn—k) +1> 0, and as l > k, we have — > 0. Consider two 2 cases. 00 • n > 2l: Then a> 0, so that R'(G) > k + > k. • n < 2l: Since a < l, we have a^-f1 > l. As l < n - k, we have R'(G) > k + — + — = k + >k. n n In both cases we have a contradiction as R'(G) < k. Now consider the case \V(G)| = \Vn-k(G)| + \Vk(G)|. Using the notation as above we get \E(G)\ = b(n - k) - s + t = ak - t + s. Since a + b = n, after dividing by n we obtain , , 2s 2t b = k +----. n n For R' (G) we get . b(n - k) - s + t R (G)= n - k + k and after substituting for b the previous expression we obtain , n - 2k n - 2k R'(G) = k + -— + t-—. n(n - k) nk a Obviously, R'(G) > k with equality only if s = t = 0. Hence, G is a bipartite graph with bipartition (Vn-k(G),Vk(G)), as required. □ We remark that, although G is bipartite if the assumptions of Lemma 4.2 are satisfied, G can possibly have multiple edges and does not need to be connected. This assumption is important as in the proof of the next lemma we possibly create multiple edges and we may disconnect the graph. CO 3 Gï O CM i CM CM CO CD ■ i-H U CD U CU Lemma 4.3. We have \V(G)| = \Vn-k(G)| + \Vk(G)|. Proof. By Lemma 4.2, we cannot have \V(G)| = \Vn-k(G)| + \Vk(G)| + 1. Thus, by way of contradiction, suppose that there are u,v £ V(G), such that k < degG(u) < degG(v) < n — k. Moreover, assume that among the vertices of V(G) \ (Vk(G) U Vn-k(G)), the vertex u has the smallest degree and v has the greatest degree. Denote A(u) = {wu £ E(G); degG(w) < degG(u)} and A(v) = {vz £ E(G); degG(v) < degG(z)}. Let a = min{|A(u)|, |A(v)|}. Remove a edges wu £ A(u) and replace them by a edges wv; remove a edges vz £ A(v) and replace them by a edges uz; and denote the resulting graph by G0. Then degG(x) = degGo(x) for every x £ V(G). Since degG(u) < degG(v), we have R'(G0) < R'(G). Denote Ao(u) = {wu £ E(Go); degGo(w) < degGo(u)} and Ao(v) = {vz £ E(Go); degGo(v) < degGo(z)}. Then either A0(u) = 0 or A0(v) = 0. Consider two cases: • A0(u) = 0: Choose wu £ A0(u), remove this edge from G0, replace it by wv and denote the resulting graph by Gi. Now degGl (u) = degGo (u) — 1 and degGl (v) = degGo (v) + 1. Since A0(u) = 0, we have A0(v) = 0, and as v has the maximum degree among the vertices of V(G) \ (Vk(G) U Vn-k(G)), edges incident with v in G0 contribute by 1 to R'(G0), and analogously edges incident with v in G1 contribute by 1 to R'(G1). Therefore, to count R'(G0) — R'(G1) it suffices to consider the edges incident with u. Denote l = |A0(u)| and d = degGo (u). As u has the minimum degree among the vertices of V(G) \ (Vk(G) U Vn-k(G)), we have R'(Gi) = R'(G0) — d + —. Since d + — = ¿jd—T) < we have R'(Gi) < R'(G0) with equality only if d = l. • A0(u) = 0: Choose uw £ E(G0), such that uw = uv, remove this edge from Go, replace it by vw and denote the resulting graph by Gi. Analogously as in the previous case, degGl (u) = degGo (u) — 1 and degGl (v) = degGo (v) + 1. As A0(u) = 0 and u has the minimum degree among the vertices of V(G) \ (Vk(G) U Vn-k(G)), the edges incident with u contribute to R' by the same value in G0 as in G1, with the possible exception of the edge uw, which is now replaced by vw, and its contribution to R'(G1) is not greater as its contribution to R'(G0). Denote l = \{vz £ E(G0); degGo(z) < degGo(v)}\ and d = degGo(v). Then R'(Gi) < R'(G0) — d + dh < R'G) with equality only if l = 0 d+1 (and degGo (w) > degGo (v)). Now define AT(u) and AT(v) analogously as A0(u) and A0(v). Observe that if A0(u) = 0 then AT(v) = 0 and if A0(u) = 0 then AT(u) = 0. Hence, repeat the process described in the previous cases to obtain G2, G3, ... until we get a graph Gr such that either degGr(u) = k or degGr (v) = n — k. In this way we decreased the number of vertices x which degree is in the open interval (k, n — k). Now repeat the process with other pair of vertices whose degree is in the interval (k,n — k) and yet another and so on. At the end we have either a single vertex with degree in (k, n — k), which contradicts Lemma 4.2, or exactly two such vertices. Thus, we can assume that G has exactly two vertices, say u and v, with k < deg(u) < deg(v) < n — k. By Lemma 4.2, we have u £ Vk(Gr) and v £ Vn-k(Gr). If R'(Gr) < R'(G), that finishes the proof of the lemma. So, we may assume that R'(G) = R'(G0) = ••• = R'(Gr). Analogously as above, consider two cases: • A0(u) = 0: Then A0(v) = 0 and degGo(u) = d = l, see the analogous case above, so that both u and v have neighbors only in Vk(Go). This means that also in Gr the vertex u has neighbors only in Vk(Gr). Hence, Vk(Gr) is not an independent set, which contradicts Lemma 4.2. • A0(u) = 0: Then l = 0, see the analogous case above, so that uv £ E(G0) and both u and v have neighbors only in Vn-k(Go). This means that in Gr the vertex v has neighbors only in Vn-k(Gr). Hence, Vn-k(Gr) is not an independent set, which contradicts Lemma 4.2. q vO m Observe that in the final contradiction of the previous proof we use the fact that Lemma 4.2 is stated for graphs which may be disconnected and which may have multiple edges. o Proof of Theorem 4-1- By Lemmas 4.2 and 4.3, G is a bipartite graph with bipartition (Vn-k(G), Vk(G)), possibly with multiple edges. Denote a = \Vk(G)| and b = \Vn-k(G)|. Then\E(G)| = ak = b(n-k), so that (a+b)k = bn. As a + b = n, we get b = k and consequently a = n — k. Hence, R'(G) = = b = k. Since there is a unique simple graph satisfying \ Vk(G)\ = n — k and \Vn-k(G)\ = k, namely Kk,n-k, the theorem is proved. □ Corollary 4.4. Let G be a triangle-free graph on n vertices with 5(G) = k, k > 1. Then R'(G) > k with equality if and only if G = Kk,n-k. Proof. Suppose that there is a vertex v in G such that degG(v) > n — k. Let u be a neighbor of v. Since G is triangle-free, NG(u) n NG(v) = 0, so that NG(u) Q V(G) \ NG(v). Hence, degG(u) < k, a contradiction. Thus, A(G) < n — k. As 5(G) < A(G), we have k < n — k, so that n > 2k. Now, consider two cases: • n> 2k: By Theorem 4.1 we have R'(G) > k with equality if and only if G = Kkn-k. • n = 2k: As n—k = k, G is a regular graph. Since \E(G)\ = kn, we have R'(G) = kn = k. Choose two vertices, say u and v, such that uv £ E(G). Since both NG(u) and NG(v) are disjoint independent sets of k vertices each, we have G = Kk,k. □ CO ' }h Acknowledgements. The research for this paper was supported by the following grants: Slovenian-Slovak Bilateral project, ARRS Research Program P1-0297, ARRS Reasearch project J1-0540, VEGA Research Grant No. 1/0871/11, and APVV Research Grant No. 0223-10. Jh References CD [1] B. Bollobas, P. Erdos, Graphs of extremal weights, Ars Combin., 50 (1998), 225-233. CO CD CD CO 5H a CD [2] G. Caporossi, P. Hansen, Variable neighbourhood search for extremal graphs 6, Analyzing Bounds for the Connectivity Index, J. Chem. Inf. Comput. Sci., 43 (2003), 1-14. [3] G. Caporossi, I. Gutman, P. Hansen, L. Pavlovic, Graphs with maximum connectivity index, Comput. Biol. Chem., 27 (2003) 85-90. [4] M. Cygan, M. Pilipczuk, R. Skrekovski, On the inequality between radius and Randic index for graphs, to appear in MATCH Commun. Math. Comput. Chem. [5] Z. Dvorak, B. Lidicky, R. iSkrekovski, Randic index and the diameter of a graph, European J. Combin., 32 (2011) 434-442. [6] S. Fajtlowicz, On conjectures of Graffiti, Discrete Math., 72 (1988) 113-118. [7] O. Favaron, M. Maheo, J. F. Sacle, Some eigenvalue properties in graphs (Conjecture of Grati - II), Discrete Math. 111 (1993), 197-220. [8] J. Gao, M. Lu, On the Randic index of unicyclic graphs, MATCH Commun. Math. Comput. Chem., 53 (2005), 377-384. [9] L. B. Kier, L. H. Hall, Molecular Connectivity in Structure-Activity Analysis, Wiley, (1986). [10] X. Li, J. Liu, Complete solution to a conjecture on the Randic index of triangle-free graphs, Discrete Math. 309 (2009), 6322-6324. [11] X. Li, Y. Shi, A survey on the Randic index, MATCH Commun. Math. Comput. Chem., 59 (2008) 127-156. [12] L. Pavlovic, I. Gutman, Graphs with extremal connectivity index, Novi. Sad. J. Math., 31 (2001), 53-58. [13] M. Randic, On characterization of molecular branching, J. Amer. Chem. Soc., 97 (1975) 6609-6615. [14] N. Trinajstic, Chemical Graph Theory, Boca Raton (1983).