IMFM Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia Preprint series Vol. 49 (2011), 1141 ISSN 2232-2094 ON THE INEQUALITY BETWEEN RADIUS AND RANDIC INDEX FOR GRAPHS Marek Cygan Michal Pilipczuk Ljubljana, March 9, 2011 On the inequality between radius and Randic index for graphs* ,fi Marek Cygan, Michal Pilipczuk"1" and Riste Skrekovski* CD March 4,2011 o u a CD U 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. Let r(G) be the radius of G. We prove that for any connected graph G of maximum degree four which is not a path with even number of vertices, R(G) > r(G). As a consequence, we resolve the conjecture R(G) > r(G) - 1 given by Fajtlowicz in 1988 for the case when G is a chemical graph. In chemical graph theory topological indices belong to the set of molecular descriptors that are 1 Introduction (N calculated based on the molecular graph of a chemical compound. In 1975 Milan Randic [10] introduced the 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., R(G) = E 1 uveE(G) Vdeg(u)deg(v) ' HH 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 the survey [8] by Li and Shi or in the book [9] by Li and Gutman. For the last two decades researchers are investigating extremal values and relations between topological indices. In 1988 Fajtlowicz [6] stated the following conjecture: CD *This work was supported by bilateral project BI-PL/08-09-008 and by Slovenian ARRS Research Program P1-0297. ^Department of Mathematics, Computer Science and Mechanics, University of Warsaw, Warsaw, Poland, {cygan@,michal.pilipczuk@students}.mimuw.edu.pl * Department of Mathematics, University of Ljubljana, Jadranska 19, 1111 Ljubljana, Slovenia, skrekovski@gmail.com Conjecture 1.1. For all connected graphs G, R(G) > r(G) — 1. Caporossi and Hansen [2] have shown that R(T) > r(T) + V2 — 3/2 for all trees T. Liu and Gutman [11] verified Conjecture 1.1 for unicyclic graphs, bicyclic graphs and chemical graphs with cyclomatic number c(G) < 5. You and Liu [12] proved that the conjecture is true for biregular graphs, tricyclic graphs and connected graphs of order n < 10. More recent results related to extremal values of the Randic index can be found in [4, 5, 7, 13, 14]. Very recently Dvorak et al. [1] have shown that for every graph R(G) > r(G)/2. Their main idea was introducing a parameter R'(G) defined as: * R (G) uv^E(G) max(de§(u)' deg(v)) ' It is easy to see that for every graph G we have R(G) > R'(G). However R'(G) proves to be very useful as it is much easier to follow during graph modifications than R(G). In this paper we investigate Conjecture 1.1 for the case when G is a chemical graph - a graph of maximum degree < 4. The main result of this paper is the following theorem. Theorem 1.2. For all connected chemical graphs G the following inequality holds: 1 R'(G) > r(G) — -. 2 As a consequence, we prove Conjecture 1.1 for the case when G is a graph of maximum degree four. Our proof uses the bound on the maximum degree of the graph only in one step. Therefore, it may be said that we develop a general framework for proving Conjecture 1.1, reducing the problem to a slightly stronger version regarding a very special type of a graph, which we call a bag (appropriate definitions can be found in section 4). This version appears to be quite easy in the chemical case; however the proof in the general case eluded us. Finally, we strengthen our result to the version of Conjecture 1.1 stated in [2], also only for chemical graphs: Theorem 1.3. If a connected chemical graph G is not a path of odd length > 3 then R(G) > r(G). It is easy to verify that Theorem 1.3 is not valid for any path P of odd length > 3 as in this case R(P) = r(P) — § + V-. 2 Preliminaries HH Throughout this paper all graphs are simple and undirected. For a graph G by V(G) we denote the set of vertices of the graph G, and by E(G) the set of edges of the graph G. By a k-vertex we denote a vertex of degree exactly k. Now, let us introduce some definitions and observations concerning bridges and the radius of a graph. An edge e e E(G) is called a bridge if removing e increases the number of connected components of G. A centre of a connected graph G is a vertex v e V(G) such that d(v, w) < r(G) for all w e V(G). Intuitively, the centre of a graph is a vertex attaining minimum in the definition of the radius of the graph. Now we state a few simple bounds on the radius of a graph. a o o c^ CO Lemma 2.1. Let G = (V, E) be a connected graph. Then r(G) < ^• Moreover, if G contains a k-vertexfor k > 3 then r(G) < |Vl-2fc-2). Proof. Let us consider a spanning tree T of G. Obviously, r(T) > r(G) as distances in G are not greater than in T. Now take the longest path P in T, consisting of d vertices. As T is a tree, the midpoint of P (or one of the midpoints if d is even) is distant by at most | to all the vertices of T, by the maximality of P. Obviously d < |V|, so r(G) < r(T) < d < iVi In order to obtain the second part of the claim let v be a k-vertex and let T be any spanning tree containing all the edges incident with the vertex v. Then the vertex v has degree k in the tree T, so the longest path P excludes at least k — 2 neighbours of this vertex. Thus r(G) < r(T) < d-(fc-2) |V | —(fc—2) n 2 < 2 . ^ A vertex v e V(G) is locally minimal (resp. maximal) if and only if deg(v) < deg(w) (resp. deg(v) > deg(w)) for all vw e E(G). We use the following lemma from [1]. For the sake of completeness, we include its proof. Lemma 2.2. If G' is derived from G by removing an edge incident with a locally minimal vertex, then R'(G') < R'(G). Proof. Let v be a locally minimal vertex and w be any of its neighbours. By G' we denote the graph G with the edge vw removed. Observe that since v is locally minimal, the only edges in G' which have a different contribution to R'(G') comparing to their contribution to R'(G) are those incident with w. Let d be the degree of the vertex w in G. The contribution of each of the d — 1 edges incident with w in G' increases by at most ^ty — i and the contribution of the edge vw to R'(G) was 1. Hence, R'(G') < R'(G) — d + (d — 1)(^ — d) = R'(G). □ CSI This immediately yields the following corollary: Lemma 2.3. If G' is derived from G by removing a locally minimal vertex, then R'(G') < R' (G). CO Now we introduce two lemmas, which enable us to 'cut' larger parts of the graph. Lemma 2.4. Let H be a connected graph and v e V (H) be such a vertex, that after the removal of v the graph H becomes a union of connected components Hy,H2 ,... ,Hk where k > 3. Then there exists an index j that if H' is derived from H by removal of Hj then H' is connected and r(H') = r(H). Proof. The fact that H is connected is obvious — all the components of H — v are adjacent to v and we remove one of them. For 1 < i < k let us denote CD ri = max dH(v,u). u£V (Hi) Let j be such an index 1 < j < k that rj is minimal. Let H' be as in the lemma statement. Observe that r(H) < maxi max^^ ri > r(H), which is not possible. Hence we have w e V(H'). Consequently, for each vertex x e V(H') we have dH/(w,x) = dH(w,x) < r(H),andso r(H') < r(H). Now we prove that the radius of the graph H' is not smaller than the radius of the graph H. Let w' be the centre of H'. We show that for each vertex u e V(H) there exists a vertex u' e V(H') such that dH(w',u) < dH/(w',u'), which proves that r(H) < r(H') since w' is the centre of H'. Observe that for each u e V(H') we have dH(w',u) = dH/(w',u), so for u e V(H') we set u' = u. Consider any vertex u e V(Hj). Since v is a cut vertex and every path between u and w' includes v we have dH(w', u) = dH(w', v) + dH(v, u) = dH/ (w', v) + dH(v, u) < dH/(w', v) + r j As k > 3 there exists an index j' = j such that w' e V(Hj/). Since rj is minimal we have rj/ > rj. Let u' be any vertex from V(Hj/) such that dH(v, u') = dH/ (v, u') = rj/. Finally we have dH(w', u) < dH/(w', v) + rj < dH/(w', v) + dH/(v, u') = dH/(w', u'). This establishes the lemma. □ Lemma 2.5. Let H be a connected graph and v e V (H) be such a vertex that after its removal the graph H becomes a union of connected components H1, H2,..., Hk. Let H' be a graph derived from H by removal of some Hi. Then R'(H') < R'(H). o Proof. We consecutively remove vertices from V(Hi) until the graph becomes H', each time ensuring that the value of R' does not increase. Note that possibly at some moments our graph is not connected. Let vmin be a vertex of minimum degree among the vertices still to be removed and vmax be a vertex of maximum degree. If deg(vmin) < deg(v) then vmin is a locally minimal vertex and can be removed due to Lemma 2.3. Assume then that deg(vmin) > deg(v), so deg(vmax) > deg(v) as well. Thus vmax is a locally maximal vertex, so 1= V _1_. VmJ^H) max(deg(vmax), deg(w)) We see that if one removes all the remaining vertices from Hi, then the value of R' will decrease by at least 1 due to removal of all the edges incident with vmax and it will increase by at most 1 — the only increase is due to the edges incident with v and not incident with Hi, and it can be at most b as in the end the whole sum EvweE(H/) max(degH/ (V),degH/(w)) is at most 1 T^fe^ in this situation we can remove all the remaining vertices and the value of R' will not increase. □ 3 Decomposition We shall prove Theorem 1.2 by contradiction. From now on we assume that G0 = (V0, is the smallest counterexample to Theorem 1.2 regarding |V01 + 1. Let us introduce a few simple lemmas, which will enable us to characterize G0. We begin with a simple observation concerning locally minimal vertices. a CD 4 Jh A o u Lemma 3.1. Suppose that v is locally minimal in G0. Then all the edges incident with v are bridges. Proof. Suppose that vw is not a bridge. By Lemma 2.2 removal of the edge vw from the graph G0 does not increase R'. Moreover, after its removal the graph remains connected and its radius cannot decrease (as all the distances can only be larger). Therefore, by removing the edge vw from the graph G0 we obtain a smaller counterexample, a contradiction. □ Observe that after removing all the bridges in a connected graph, it becomes a union of connected components of size at least 3 not containing bridges (called further bridgeless components) and isolated vertices. Let us introduce a notion of bridge decomposition: a graph is decomposed into a tree, where the set of nodes of the tree consists of bridgeless components connected by paths comprised of bridges. See Fig 1 for an illustration. For a graph G = (V, E) let E' C E be the set of bridges. Consider the graph G' = (V,E \ E'). By K(G) = [Hl,...,Hk } we denote the set of connected components of the graph G' containing at least three vertices. 0 o 1 CO £ CO CO CO CD Jh CD CO u a CD U Figure 1: A connected graph G and a tree derived from G by identifying all components Hj e K(G) into single vertices, which are presented as encircled nodes. Lemma 3.2. For any vertex v of the graph G0 there are at most two bridges incident to the vertex v. Proof. Observe that if v is a cut-vertex of G0, then removing v splits G0 into exactly two connected components — otherwise by Lemmas 2.4 and 2.5 one of these components could be removed without decreasing radius and without increasing R', so we would obtain a smaller counterexample. Hence there are at most two bridges incident to the vertex v. □ Let E' C E be the set of bridges of G0. Since we cannot have a cycle made of bridges, by Lemma 3.2 the edges E' form a set of paths. These paths end in the leaves of G0 or in the bridgeless components K(G0). Let us denote this set of paths by B(G0). Lemmas 3.1,3.2 justify the following decomposition theorem. Theorem 3.3. Let G0 = (V0, E0) be a minimal counterexample to Theorem 1.2. Then: 1. G0 is a tree of bridgeless components Hi e 'K(Go), connected by paths from the set B(G0), and with possible additional paths from BB(G0) attached to them. 2. Every path from BB(G0) either connects two distinct components or is attached to one o component 3. The end-vertices of paths from B(G0) leaving a given bridgeless component are distinct. 4. Removal of every edge that is not a bridge increases R'(G0). Proof. Let us decompose Go into bridgeless components H(G0). By Lemma 3.2 the bridges of Go can form only a set of paths. Thus G0 can be expressed as a set of bridgeless components connected by paths from B(G0) and with paths from B(G0) attached. Moreover, the end-vertices of paths from B(G0) leaving a bridgeless component are distinct, because otherwise we would have a forbidden cut-vertex splitting the graph into at least 3 components. To prove that removal of each edge that is not a bridge increases R'(G0), observe that otherwise after removal of such an edge the radius would not decrease, therefore we would obtain a smaller counterexample. □ 4 Bridgeless components Now we will resolve the case of a single bridgeless component from decomposition obtained in Theorem 3.3. Such a structure will be called a bag. We would be able to proceed with bags simply as subgraphs of G0 induced by bridgeless components along with vertices at distance 1 from them, however we choose to introduce an abstract definition of a bag in order to establish a framework, which could be helpful in proving the general version of Conjecture 1.1. I Definition 4.1. A connected graph H is a bag if: CO 2 (1) after removal of vertices of degree 1 it becomes a bridgeless component (denoted further by C (H), the core of a bag), (2) each vertex has at most one neighbour of degree 1, (3) removal of each edge of C(H) increases R' (H). HH Firstly, let us observe the following properties of the bags: Lemma 4.2. If H is a bag then: (1) no vertex of C (H) is locally minimal, HH (2) H does not contain 2-vertices, CO (3) each 3-vertex has exactly one pendant neighbour, (4) 3-vertices are not adjacent. CO u a CD U o u a CD U Proof. To prove (1) observe that if v e V(C(H)) is locally minimal, then all the edges incident with v would have to connect v with pendant vertices, due to property (3) of a bag and Lemma 2.2. So v would have to be the only vertex of C(H), but it has at least 3 vertices. In order to obtain (2) observe that a vertex v of degree 2 cannot have two pendant neighbours (then it would be the only vertex of C(H)) and it cannot have one pendant neighbour (then C(H) would contain a bridge incident with v). So both of the edges incident with v connect it to other vertices of C(H), having degree at least 2 by the definition of C(H). Thus v is locally minimal, a contradiction. To show (3) observe that if a 3-vertex has no pendant neighbour, then it is locally minimal as there are no 2-vertices in H. Moreover, each vertex has at most one neighbour of degree 1 by property (2) of a bag. To verify (4) assume that deg(v) = deg(w) = 3 and vw e E(H). Obviously vw e E(C (H)), so vw is not abridge. Let us calculate the change of R'(H) after the removal of vw: • We have — | due to the loss of the contribution of the edge vw. • The contribution of remaining two edges incident with v can increase, but only from | to 1 if the corresponding neighbour had degree at most 2. But there are no 2-vertices, so only the contribution of edges connecting v to pendants can increase. Both remaining neighbours of v cannot be pendants at the same time, because in this situation vw would be a bridge in C(H). So the increase of the contribution of these edges can be at most XJ i _ i = 1 2 3 6' (N • Analogously, the increase of the contribution of the remaining two edges incident with w can be at most 1. CO Therefore, after the removal of vw, the change of R' is at most — 1 + 1 + 6 = 0, which is a contradiction with property (3) of a bag. □ Now we are ready to prove that for chemical bags (namely bags with maximum degree at CO most 4) even stronger form of Theorem 1.2 holds. This stronger form will be crucial in the CO general case. As in the further proof we do not use the bound on the maximum degree of the graph, the following lemma stated for general bags would imply Conjecture 1.1 in full generality. Proposition 4.3. If H is a chemical bag, then R'(H) > r(C(H)) + 1. Proof. Denote by vi the number of i-vertices in H. By (2) of Lemma 4.2 we know that vY + v3 + v4 = |V(H)| and v3 + v4 = |V(C(H))|. Observe that H has exactly vi+3v|+4v4 edges. Let ei,j be the number of edges in H with one end-vertex of degree i and the other of degree j. By further use of Lemma 4.2, we infer that: .CD • ei,3 = v3, • ei,4 = vi — v3, e3,4 + e4,4 = vi+3v23 +4v4 — vi. The contribution to R' of each edge is either 1 or |. Thus , v3 1/ vi +3v3 +4v4 \ v3 vi + 3v3 + 4v4 = — + o o 00 CSI CSI D'/m v3 1 / vi +3v3 +4v4 \ R (H) = "g3 + 4 ( vi - v3 + -2--vi ) 2 J 12 8 _ v3 + v4 + vi - v3 + v3 2 8 12. Observe that by Lemma 4.2(3) the number vi — v3 is always nonnegative, as every 3-vertex has exactly one pendant neighbour. Thus R'(H) > v3+V4. Suppose that there is a 4-vertex which does not have a pendant neighbour. Then it has degree 4 in C(H) and from Lemma 2.1, we conclude that r(C(H)) < V3+24-2. Thus R'(H) = ^ + ^ + H > ^ = ^lif—1 + 1 > r(C(H)) + 1, and we are done. We are left with the case when all the vertices of the core have pendant neighbours. That means that vi = v3 + v4 and in C(H) all the vertices are of degrees 2 or 3. Note that as the core has at least three vertices and 3-vertices in H (2-vertices in C(H)) are not connected, there must be at least one 4-vertex in H (which is a 3-vertex in C(H)). The sum of degrees of vertices of a graph is always even, so there must be at least two of them. Obviously, the number of vertices in C(H) is at least 4, because we have a 3-vertex in C(H). Observe that if there exists a vertex in C(H) connected to all the other vertices, then r(C(H)) = 1 and thus R'(H) > v3+V4 > 2 = r(C(H)) + 1 — we are done. Now we assume that every vertex of C(H) is not connected to all the other vertices. In this situation there are at least 5 vertices in C(H), because we have a 3-vertex, three its neighbours and at least one other vertex. At least two of these vertices are of degree 3 in C (H), so v3 + v4 > 5 and v4 > 2. Therefore, vi — v3 v3 _ v4 v3 _ v4 V3 + v4 2 5 1 8 12 _ 8 12 _ 24 12 > 24 12 _ 2' CO By Lemma 2.1, we conclude that r(C(H)) < — as there is at least one 3-vertex in C(H), so g R'(H) = ^ + ^ + H > ^ + 1 = ^Lif—1 +1 > r(C(H)) + 1. Thus we are done in this case as well. □ 5 The general case • i Now using the decomposition from Theorem 3.3, we construct a tree T containing all the important information about the graph G0. Let B e H(G0) be a bridgeless component and let rB be its radius. Moreover, let V' C V(B) be the set of vertices of B that are incident with bridges in G0. Remove all the vertices from the set V (B) \ V' and add a central vertex vB. Connect the central vertex vB to each vertex a A o u ti Figure 2: A graph G and its derived tree T with components of G replaced by star-like graphs. Centers of the star-like subgraphs are encircled. Vertices on the additional paths of length rB + 1 are smaller. 0 o 1 CO ^ CO CO CO CD Jh CD CO u a CD U v G V' be a path of length rB. Additionally, attach two paths of length rB + 1 to the central vertex vB. See Fig 2 for an illustration. Theorem 3.3 assures that graph T constructed in this manner will be indeed a tree. Lemma 5.1. The following inequality holds: r(T) > r(Go). Proof. Let vT be the centre of the tree T. Observe that as during the construction there were two paths of equal length attached to every central vertex, if vT is on these attached paths it means that vT = vB for some B. We choose a vertex v G V0 as follows: • if vT G V0 then let v = vT, • if vT lies on a path added for some bridgeless component B connecting vB with u — the end-vertex of some outgoing path from B(G0), then let w be the centre of the component B. We know that dGo (u, w) < rB so one can choose a shortest path between u and w and take v from it such that dGo(u,v) < dT(u,vT) and dGo(v,w) < dT(vT,vB). In particular, we let v = w, if vT = vB. Now take any vertex u G V0. We shall prove that one can find a path between u and v in G0 that is not longer than r(T). We choose uT in V(T) as follows: • if u G V (T) then let uT = u, • if u lies in a bridgeless component B then let uT be a vertex on one of the two additional paths attached to vB, in the same distance from vB as u was from the centre of B. To prove the lemma it is enough to show, that we can transform the shortest path between vT and uT in the tree T into a walk between v and u in the graph G0 of non greater length. Indeed, in such a situation we would have that r(T) > dT(vT, uT) > dGo (v, u) and, as u was arbitrarily chosen, this would prove that r(T) > r(G0). Let P be the shortest path from vT to uT in the tree T. We construct a walk P' in the graph G0. Consider the first edge of the path P. • If the first edge of the path P corresponds to a bridge in G0, which means that it belongs to some path in B(G0), in the walk P' we use the corresponding bridge. ,fi o u • Now we consider the maximal prefix of the path P, which does not use an edge of the tree T which corresponds to a bridge in G0. Observe that the path P ends either in a vertex belonging to both sets V0, V (T) or belonging to an attached path of length rB +1. In both cases we can construct a corresponding fragment of the walk P' going through the centre of the bridgeless component B, which will be of non greater length. We continue in this manner with the following edges of the path P: each time we either use a bridge in the graph G0 or replace a maximal fragment not using bridges from G0 with a walk going through the centre of the bridgeless component. In the end we obtain the desired walk P', which concludes the proof. □ 0 o 1 CO £ CO CO m CD Jh CD m u a CD U Figure 3: A graph G and its derived tree T with components of G replaced by star-like graphs together with a marked longest path in T. For the marked longest path in T we have d0 = 1, ri = 1, di = 1, ri = 2, d§ = 2, r2 = 1, d3 = 1. Now we are ready to finish the proof of Theorem 1.2. Take the longest path in T and denote it by P. This path consists of alternately paths from ®(G0) connecting bridgeless components in G0 (or attached to bridgeless components) and joined pairs of radii connecting central vertices of stars (replacing bridgeless components) with their boundaries. We denote the lengths of paths originated in G0 by d0, d1,..., dk (in order of the appearance on P) and the radii of the bridgeless components by r1, r2,..., rk. Denote these bridgeless components by B1, B2,..., Bk. If the path P starts (resp. ends) with an attached path of length rB + 1 for some B, we simply assume that d0 = 1 (resp. dk = 1). Thus the length of P is equal to l = ^k=0 di + ^k=1 2r^ (see Fig 3). If k = 0 then the whole graph G0 is a path of length d0 with R'(G0) = if d0 > 1 and R'(G0) = 1 if d0 = 1. In this situation r(G0) = [d0] so we are done. From now assume that k > 0. For every 1 < i < k with Bi we associate a chemical bag Hi: Hi is a graph induced in G0 by V(Bi) and vertices in distance 1 from Bi. Let us formally check that the graphs Hi are chemical bags, using Theorem 3.3: (1) The only pendants in Hi are vertices in distance 1 from Bi, so C(Hi) component. Bi is a bridgeless (2) The end-vertices of paths outgoing from Bi are distinct, so every vertex has at most one pendant neighbour. (3) Removal of every edge vw from Bi increases R'(Go). The degrees of v, w are the same in G0 and in Hi so the losses of contribution from vw to R'(G0) and to R'(Hi) are equal. However, the neighbours of v and w have non greater degree in Hi than in G0 so the increase of the contributions from the edges incident with v and w will be larger in Hi than in G0. Therefore, removal of vw increases R'(Hi) as well. (4) Hi are induced subgraphs of a chemical graphs, so they are chemical as well. By Proposition 4.3 we conclude that R'(Hi) > r(Bi) + 1 = ri + 1. Thus k k k—1 k l < £ di + Y 2(R'(Hi) — 1) = (d0 — 1) + — 2) + (dk — 1) + £ 2R'(Hi). i=0 i=1 i=1 i=1 Now we construct G' from G0 by cutting out all the irrelevant parts of the graph: we cut out everything apart from bags Hi and parts of path P originated in the graph G0. Note that these cuts can be expressed as applications of Lemma 2.5 to vertices in distance 1 from components Bi. Therefore R'(G') < R'(G0). Now let us calculate R'(G'). Observe that R'(G') consists of contributions of all Hi's and paths connecting them (plus the first and the last attached paths). Assume that di > 2 for some 1 < i < k — 1. Then the contributions of the first and last edge of the i-th path to R'(G') is the same as the contributions to R'(Hi) and R'(Hi+1), respectively. The contributions to R'(G') of all di — 2 remaining edges are equal to 2. Similarly, if i = 0 or i = k then the contribution to R'(G') of the last or first edge, respectively, is equal to its contribution to R'(Hy) or R'(Hk), respectively, and all the remaining di — 1 edges have contributions equal to 1. The only left case is when di = 1 for some 1 < i < k — 1. In this case subgraphs Hi and Hi+1 share this edge and its contribution to the R'(G') is equal to its contribution to R'(Hi) o csr or R'(Hi+1), depending which end-vertex of the edge has larger degree. However, both the contributions of this edge to R'(Hi) or R'(Hi+1) are at most 1, so the contribution to R'(G') is not smaller than the sum of contributions to R'(Hi) and R'(Hi+1) plus — 2 = . From this we conclude that CO k—1 k R'(G') > ^ + £ ^ + ^ + Y R'(Hi) > 2. k-1 2 i=1 i=1 As r(T) = [2] and l is an integer, r(T) < 2 + 1. Therefore R'(G0) > R'(G') > 2 > r(T) — 1 > r(G0) — 1, which finishes the proof of Theorem 1.2. □ • i 6 From R' to Randic index R As for every graph G it holds R'(G) < R(G), we have proven that for chemical graphs R(G) > r(G) — 1. We can slightly strengthen this result to prove Theorem 1.3, i.e. if a connected chemical graph G is not a path of odd length greater than 2 then R(G) > r(G). a CD 11 A o u ti Proof of Theorem 1.3 Observe that for all a G {1, 2,3,4} and b G {1,2, 3, 4} the following inequality holds: ' _1___1_\2 J___1 ra Vb) < Vab max(a, b)' (6.1) Obviously, the equality holds for a = b. Simple calculations of all 6 relevant cases (without losing generality a < b) show that the term RHS — LHS, which is right hand side minus left hand side of (6.1), is always positive: a 1 1 1 2 2 3 b 2 3 4 3 4 4 RHS — LHS > 0.1213 0.0653 0.0000 0.0580 0.0606 0.0326 0 o 1 CO £ CO CO CO CD Jh CD CO u a CD U Observe that if | V| = 1, then r(G) = R(G) = 0 so the theorem holds. Now suppose that all the vertices of G have degrees 1 or 2. As G is connected it is a cycle or a path. We will use an alternative formula introduced by Caporossi et al. [3] for the Randic index of a connected graph on at least two vertices: RG) = EP — 1 E 1 1 2 vweE(G) ■sj deg(v) a/ deg(w) (6.2) If G is a cycle then it is a regular graph, so R(G) = |V(2G)| > r(G) due to Lemma 2.1. If G is a pathoflength 1 then r(G) = 1 = R(G). If G is a path of even length > 2 then r(G) = |V and R(G) = ^ — (1 — ^)2 > ^ — (2)2 > r(G). We are left with the case in which there exists at least one vertex of degree > 3. By Lemma 2.1 we know that r(G) < |V(G,)|-1. Applying inequality (6.1) to a = deg(v) and b = deg(w) for all edges vw G E(G) and using equation (6.2) we conclude that R(G) = |V (G)| 1 2 2 1 1 ■\J deg(v) -\J deg(w) > |V (G)| 1 ^ 2 vwGE(G) ^/deg(v) deg(w) max(deg(v), deg(w)) IV (G)| R(G_)+ ' Therefore /IV (G)| — R(G^ < R(G) — R'(G). If |V (G)| 2 However if — R(G) < 2 then, by Lemma 2.1, R(G) > |V(G2)|-1 > r(G) and we are done. — R(G) > 2 then R(G) > R'(G) + 1 > r(G) — 2 + 1 > r(G) due to |V (G)| Theorem 1.2, and we are done as well. This establishes the theorem. □ 2 2 1 1 2 References [1] Z. Dvorak, B. Lidicky, R. Skrekovski, Randic index and the diameter of a graph, to appear in European Journal of Combinatorics. [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. Aouchiche, P. Hansen, M. Zheng, Variable neighbourhood search for extremal graphs 18: conjectures and results about Randic: index, MATCH Commun. Math. Comput. Chem. 56 (2007) 541-550. [5] Z. Du, B. Zhou, N. Trinajstic, On Randic Indices of Chemical Trees and Chemical Unicyclic Graphs, MATCH Commun. Math. Comput. Chem. 62 (2009) 131-142. g ra S.FaJ_,Onco_eso^M,D_Ma, 72 (1988) 113-118. [7] J. Gao, M. Lu, On the Randic: index of unicyclic graphs, MATCH Commun. Math. Comput. Chem. 53 (2005) 377-384. [8] X. Li, Y. Shi, A survey on the Randic index, MATCH Commun. Math. Comput. Chem. 59 (2008)127-156. i CSI [9] X. Li, I. Gutman, Mathematical Aspects of Randic-Type Molecular Structure Descriptors, CO ^aM Cta^y M°nographs N