A note on the minimum reduced reciprocal Randi´c index of n-vertex unicyclic graphs AKBAR ALI†,‡,∗ & AKHLAQ AHMAD BHATTI† †Department of Sciences & Humanities, National University of Computer & Emerging Sciences, B-Block, Faisal Town, Lahore-Pakistan. ‡Department of Mathematics, University of Gujrat, Gujrat-Pakistan. ∗Corresponding author: [email protected] ABSTRACT 6 1 ThegraphhavingtheminimumreducedreciprocalRandi´cindexischaracterizedamong 0 the class of all unicyclic graphs with fixed number of vertices. 2 n Keywords: Topological index; reduced reciprocal Randi´c index; unicyclic graph. a J 5 INTRODUCTION 1 ] O All the graphs considered in the present study are simple, finite, undirected and connected. C ThevertexsetandedgesetofagraphGwillbedenotedbyV(G)andE(G)respectively. The . degree of a vertex u ∈ V(G) and the edge connecting the vertices u and v will be denoted by h t d and uv respectively. Undefined notations and terminologies from (chemical) graph theory a u m can be found in (Harary, 1969; Trinajsti´c, 1992). [ Topological indices are numerical parameters of a graph which are invariant under graph 1 isomorphisms. Randi´c (1975) proposed the following topological index: v 4 R(G) = (cid:88) (d d )−1 4 u v 2 0 uv∈E(G) 4 0 for measuring the extent of branching of the carbon-atom skeleton of saturated hydrocarbons . 1 and he named it as branching index. Nowadays, this topological index is also known as 0 6 connectivity index and the Randi´c index. According to Gutman (2013), “the Randi´c index is 1 the most investigated, most often applied, and most popular among all topological indices. : v Hundreds of papers and a few books are devoted to this topological index”. i X On the other hand, many physico-chemical properties of chemical structures are depen- r dent on the factors different from branching. In order to take these factors into account, a Estrada et al. (1998) introduced a modified version of the Randi´c index and called it as atom-bond connectivity (ABC) index. This index is defined as: (cid:114) (cid:88) d +d −2 u v ABC(G) = . d d u v uv∈E(G) Details about the chemical applicability and mathematical properties of this index can be found in the survey (Gutman, 2013), recent papers (Ahmadi et al., 2014; Dimitrov, 2014; Goubko et al., 2015; Palcios, 2014; Raza et al., 2015) and the references cited therein. 1 Inspired by work on the ABC index Furtula, Graovac & Vukicˇevic´ (2010) gave the fol- lowing modified version of the ABC index (and hence a modified version of Randi´c index) under the name augmented Zagreb index (AZI): (cid:88) (cid:18) d d (cid:19)3 u v AZI(G) = . d +d −2 u v uv∈E(G) The prediction power of AZI is better than ABC index in the study of heat of formation for heptanes and octanes (Furtula et al., 2010). Details about this index can be found in the survey (Gutman, 2013), recent papers (Ali, Bhatti & Raza, 2016; Ali, Raza & Bhatti, 2016; Huang & Liu, 2015; Zhan et al., 2015) and the references cited therein. In(Mansoet al.,2012),anewtopologicalindex(namelyFi index)wasproposedtopredict the normal boiling point temperatures of hydrocarbons. In the mathematical definition of Fi index two terms are present. Gutman, Furtula & Elphick (2014), recently considered one of these terms which is given below: (cid:88) (cid:112) RRR(G) = (d −1)(d −1), u v uv∈E(G) and they named it as reduced reciprocal Randi´c (RRR) index. In the current study, we are concerned with this recently introduced modified version of the Randi´c index. In order to get some preliminary information on whether this index possess any potential applicability in chemistry (especially in QSPR/QSAR studies) Gutman, Furtula & Elphick (2014) tested the correlating ability of several well known degree based topological indices (along with RRR index) for the case of standard heats (enthalpy) of formation and normal boiling points of octane isomers, and they concluded that the AZI and RRR index has the best and second- best (respectively) correlating ability among the examined topological indices (it is worth mentioning here that, among the examined topological indices ABC was also included which was the second-best degree based topological index according to the earlier study (Gutman & Toˇsovi´c, 2013)). Hence it is meaningful to study the mathematical properties of the RRR index, especially bounds and characterization of the extremal elements for different graph classes. In (Gutman et al., 2014), the structure of n-vertex tree having maximum RRR index and the extremal n-vertex graphs with respect to RRR index were reported. An n-vertex (connected) graph G is unicyclic if it has n edges. Some extremal results for the unicyclic graphs can be found in the papers (Gan et al., 2011; Gao & Lu, 2005; Pan et al., 2006; Zhan et al., 2015). The main purpose of the present note is to characterize the n-vertex unicyclic graph having minimum RRR index over the collection of all n-vertex unicyclic graphs. MAIN RESULT Denote by S+ the unique unicyclic graph obtained from the star graph S by adding an n n edge between any two pendent vertices. Many topological indices (e.g. ABC index, R index, AZI etc.) which have S as an extremal graph over the set of all n-vertex trees, have also n S+ as an extremal graph over the set of all n-vertex unicyclic graphs. However, different n 2 approaches required to prove these results. From the definition of RRR index, it can be easily seen that RRR(T ) ≥ RRR(S ) = 0 where T is any n-vertex tree. Is it true that the n n n graph S+ has the minimum RRR index over the set of all n-vertex unicyclic graphs? The n answer is not positive; for the n-vertex unicyclic graph H+ (depicted in Fig. 1(b)), one have √ √ n √ RRR(H+) = 1+ 2(2+ n−4) but on the other hand RRR(S+) = 1+2 n−2 and n n  < RRR(H+) if 5 ≤ n ≤ 19,  n RRR(S+) = RRR(H+) if n = 20, n n  > RRR(H+) if n ≥ 21. n Fig. 1: (a) The n-vertex unicyclic graph H where n is at least 6. (b) The n-vertex unicyclic n graph H+ where n is at least 5. n In the following theorem we characterize the n-vertex unicyclic graph having minimum RRR index over the collection of all n-vertex unicyclic graphs for n ≥ 4. Theorem 1. For any unicyclic graph U where n ≥ 4, the following inequalities hold: n (cid:40) √ ≥ 1+2 n−2 if 4 ≤ n ≤ 16, RRR(U ) √ √ n ≥ 1+3 2+ n−5 if n ≥ 17. The first equality holds if and only if U ∼= S+ and the second equality holds if and only if n n ∼ U = H (where H is shown in Fig. 1(a)). n n n √ Proof. Routine computation yields RRR(C ) = n > 1 + 2 n−2 for all n ≥ 4 and √ √ n ∼ RRR(C ) = n > 1 + 3 2 + n−5 for all n ≥ 7, so we assume U (cid:54)= C . Let P(U ) = n n n n {u ,u ,u ,...,u } be the set of all pendent vertices in U . For 1 ≤ i ≤ p − 1, suppose 0 1 2 p−1 n that v is adjacent with u and W is the set of all pendent neighbors of v different from u . i i ui i i Choose a member of P(U ), say u (without loss of generality), such that n 0 1. the number of elements in W is as large as possible; u0 2. subject to (1), d is as small as possible. v0 Let d = x and N(v ) = {u ,u ,u ,...,u ,u ,...,u } where d = 1 for 0 ≤ i ≤ p − 1 v0 0 0 1 2 p−1 p x−1 ui and d ≥ 2 for p ≤ i ≤ x−1 (see Fig. 2). ui 3 Fig. 2: The presentation of an n-vertex unicyclic graph U used in the proof of Theorem 1. n If U(cid:48) is the graph obtained from U by removing the vertex u , then n−1 n 0 x−1 (cid:88)(cid:104)(cid:112) (cid:112) (cid:105) RRR(U ) = RRR(U(cid:48) )+ (x−1)(d −1)− (x−2)(d −1) (1) n n−1 ui ui i=1 We will discuss three cases: Case 1. Either the vertex v is adjacent with at least two non-pendent vertices or v 0 0 is adjacent with exactly one non-pendent vertex u such that d ≥ 5 (that is either x−1 ux−1 p ≤ x−2 or p = x−1,d ≥ 5). ux−1 Let U(1) be the collection of all those n-vertex unicyclic graphs (different from C ) which fall n n in this case. By using induction on n, we will prove that the only one graph, namely S+, n has the minimum RRR value among all the members of U(1). [Then the desired result will n follow from the fact that √ √ √ RRR(S+) = 1+2 n−2 > 1+3 2+ n−5 = RRR(H ) for all n ≥ 17.] n n For n = 4, there are only two non-isomorphic unicyclic graphs namely C and S+ and hence n n the result holds for n = 4. For n = 5, all the non-isomorphic members of U(1) are depicted n in the Fig. 3 along with their RRR values. Fig. 3: All the non-isomorphic members of U(1) together with their RRR values. 5 Now, suppose that U ∈ U(1) and n ≥ 6. By virtue of inductive hypothesis and from n n Equation (1), one have √ √ √ x−1 (cid:0) (cid:1)(cid:88)(cid:112) RRR(U ) ≥ 1+2 n−3+ x−1− x−2 d −1, (2) n ui i=1 4 with equality if and only if U(cid:48) ∼= S+ . We discuss two subcases: n−1 n−1 Subcase 1.1. If p ≥ 2. Then from Inequality (2) it follows that √ √ √ x−1 (cid:0) (cid:1)(cid:88)(cid:112) RRR(U ) ≥ 1+2 n−3+ x−1− x−2 d −1 (3) n ui i=p According to the definition of U ∈ U(1), either p ≤ x−2 or p = x−1,d ≥ 5. If p ≤ x−2, n n ux−1 then Inequality (3) implies that √ √ √ (cid:0) (cid:1) RRR(U ) ≥ 1+2 n−3+ x−1− x−2 (x−p) n √ √ √ (cid:0) (cid:1) ≥ 1+2 n−3+2 x−1− x−2 √ √ √ √ (cid:0) (cid:1) ≥ 1+2 n−3+2 n−2− n−3 = 1+2 n−2. √ The equality RRR(U ) = 1 + 2 n−2 holds if and only if x = n − 1,x − p = 2 and n U(cid:48) ∼= S+ . n−1 n−1 If p = x−1 and d ≥ 5, then the graph U(cid:48) must be different from S+ and hence ux−1 n−1 n−1 from Equation (1), one have √ √ √ (cid:0) (cid:1) RRR(U ) > 1+2 n−3+2 x−1− x−2 n √ √ √ (cid:0) (cid:1) > 1+2 n−3+2 n−3− n−4 (since in this case x < n−2) √ > 1+2 n−2. Subcase 1.2. If p = 1. Then, from the definition of u , it follows that the set W is empty 0 ui for all u ∈ P(U ). It means that no two pendent edges are adjacent. i n If x ≥ 4, then among the vertices u ,u ,...,u at least two are disconnected in U −v 1 2 x−1 n 0 (because otherwise U contains more than one cycle, a contradiction. See Fig. 4 for the n graphs U −v and U considered in this subcase). n 0 n Fig. 4: The graphs U and U −v used in Subcase 1.2 of the proof of Theorem 1. n n 0 Without loss of generality, let u and u are disconnected in U −v and suppose that C 1 2 n 0 i (for i = 1,2) is the component of U − v containing u (for i = 1,2). Since d ≥ 2 in U n 0 i ui n for all i (1 ≤ i ≤ x−1), so both the components C and C must be non-trivial. Note that 1 2 5 at least one of C and C must be a tree (for otherwise U contains more than one cycle, a 1 2 n contradiction). Let C is a tree. Since every non-trivial tree contains at least two pendent 1 vertices and no two pendent edges of U are adjacent, so there exist w ∈ V(C ) ∩ P(U ) n 1 1 n and w w ∈ V(C )∩E(U ) such that d = 2 in U , which contradicts the definition of u . 1 2 1 n w2 n 0 Hence x = 2 or 3. It should be noted that the graph U(cid:48) is different from S+ in this case. n−1 n−1 Now, we consider further two subcases: Subcase 1.2.1. If x = 2. Then from the Inequality (1), we have √ (cid:112) RRR(U ) > 1+2 n−3+ d −1 n √ u1√ ≥ 3+2 n−3 > 1+2 n−2. Subcase 1.2.2. If x = 3. Then from the Inequality (1), it follows that √ (cid:16)√ (cid:17)(cid:16)(cid:112) (cid:112) (cid:17) RRR(U ) > 1+2 n−3+ 2−1 d −1+ d −1 n u1 u2 √ (cid:16)√ (cid:17) ≥ 1+2 n−3+2 2−1 √ > 1+2 n−2, because n ≥ 6. Therefore, for any U ∈ U(1) we have RRR(U ) ≥ RRR(S+) with equality if and only if n n n n U ∼= S+. n n Case 2. The vertex v is adjacent with exactly one non-pendent vertex u such that 0 x−1 d = 3 or 4 (that is p = x−1 and d = 3 or 4). ux−1 ux−1 Let U(2) be the family of all those n-vertex unicyclic graphs (different from C ) which fall n n in this case. Note that n must be at least five in this case. By using induction on n, we will prove that the only one graph, namely H+, has the minimum RRR value among all the n members of U(2). [Then the desired result will follow from the fact that n (cid:40) √ √ (cid:112) 1+2 n−2 for 5 ≤ n ≤ 16, RRR(H+) = 1+2 2+ 2(n−4) > √ √ n 1+3 2+ n−5 for n ≥ 17.] It can be easily seen that U(2) has only one element namely H+. For n = 6, all the non- 5 5 isomorphic members of U(2) are depicted in the Fig. 5 along with their RRR values. n Fig. 5: All the non-isomorphic members of U(2) together with their RRR values. 6 6 Hence the result holds for n = 5,6. Suppose that U ∈ U(2) and n ≥ 7. By using the n n inductive hypothesis in the Equation (1), we have √ √ √ x−1 (cid:112) (cid:0) (cid:1)(cid:88)(cid:112) RRR(U ) ≥ 1+2 2+ 2(n−5)+ x−1− x−2 d −1, (4) n ui i=1 with equality if and only if U(cid:48) ∼= H+ . We consider two subcases: n−1 n−1 Subcase 2.1. If p ≥ 2. Then from Inequality (4) it follows that √ √ √ x−1 (cid:112) (cid:0) (cid:1)(cid:88)(cid:112) RRR(U ) ≥ 1+2 2+ 2(n−5)+ x−1− x−2 d −1 (5) n ui i=p According to the definition of U ∈ U(2), p = x−1 and d = 3 or 4. Hence from Equation n n ux−1 (5), it follows that √ √ √ (cid:112) (cid:0) (cid:1)(cid:112) RRR(U ) ≥ 1+2 2+ 2(n−5)+ x−1− x−2 d −1 n √ √ √ √ ux−1 (cid:112) (cid:0) (cid:1) ≥ 1+2 2+ 2(n−5)+ 2 x−1− x−2 √ √ √ √ (cid:112) (cid:0) (cid:1) ≥ 1+2 2+ 2(n−5)+ 2 n−4− n−5 (since x ≤ n−3) √ (cid:112) = 1+2 2+ 2(n−4). √ (cid:112) The equality RRR(U ) = 1+2 2+ 2(n−4) holds if and only if x = n−3,d = 3 and n ux−1 U(cid:48) ∼= H+ . n−1 n−1 Subcase 2.2. If p = 1. Then, x = 2 because p = x−1. It is easy to see that the graph U(cid:48) is different from H+ in this case. From the Inequality (1), we have n−1 n−1 √ (cid:112) (cid:112) RRR(U ) > 1+2 2+ 2(n−5)+ d −1 n √ u1√ (cid:112) (cid:112) ≥ 1+3 2+ 2(n−5) > 1+2 2+ 2(n−4). Therefore, for any U ∈ U(2) we have RRR(U ) ≥ RRR(H+) with equality if and only if n n n n U ∼= H+. n n Case 3. The vertex v is adjacent with exactly one non-pendent vertex u such that 0 x−1 d = 2 (that is p = x−1 and d = 2). ux−1 ux−1 Let U(3) be the class of all those n-vertex unicyclic graphs (different from C ) which fall in n n this case. Note that n must be at least 6 in this case. By using induction on n, we will prove that the only one graph, namely H , has the minimum RRR value among all the members n of U(3). [Then the desired result will follow from the fact that n √ √ √ RRR(H ) = 1+3 2+ n−5 > 1+2 n−2 for 6 ≤ n ≤ 16.] n It can be easily seen that U(3) has only one member, namely H . For n = 7, all the non- 6 6 isomorphic members of U(3) are depicted in the Fig.6 along with their RRR values. n 7 Fig. 6: All the non-isomorphic members of U(3) together with their RRR values. 7 Hence the result holds for n = 6,7. Suppose that U ∈ U(3) and n ≥ 8. By virtue of n n inductive hypothesis and from Equation (1), one have √ √ √ √ x−1 (cid:0) (cid:1)(cid:88)(cid:112) RRR(U ) ≥ 1+3 2+ n−6+ x−1− x−2 d −1, (6) n ui i=1 with equality if and only if U(cid:48) ∼= H . We consider two subcases: n−1 n−1 Subcase 3.1. If p ≥ 2. Then from Inequality (6) it follows that √ √ √ √ x−1 (cid:0) (cid:1)(cid:88)(cid:112) RRR(U ) ≥ 1+3 2+ n−6+ x−1− x−2 d −1 (7) n ui i=p By the definition of U ∈ U(3), p = x−1 and d = 2. Hence from Equation (7), it follows n n ux−1 that √ √ √ √ RRR(U ) ≥ 1+3 2+ n−6+ x−1− x−2 n √ √ ≥ 1+3 2+ n−5. The last inequality holds because x ≤ n − 4. Furthermore, the equality RRR(U ) = 1 + √ √ n 3 2+ n−5 holds if and only if x = n−4 and U(cid:48) ∼= H . n−1 n−1 Subcase 3.2. If p = 1. Then, x = 2 because p = x−1. Observe that the graph U(cid:48) is n−1 different from H in this case. From the Inequality (1), we have n−1 √ √ (cid:112) RRR(U ) > 1+3 2+ n−6+ d −1 n √ √ u1√ √ = 2+3 2+ n−6 > 1+3 2+ n−5. Therefore, for any U ∈ U(3) we conclude that RRR(U ) ≥ RRR(H ) with equality if and n n n n ∼ only if U = H . This completes the proof. n n REFERENCES Ahmadi, M. B., Dimitrov, D., Gutman, I. & Hosseini, S. A. 2014. Disproving a conjecture on trees with minimal atom-bond connectivity index. MATCH Communi- cations in Mathematical and in Computer Chemistry 72: 685-698. 8 Ali, A., Bhatti, A. A. & Raza, Z. 2016 (in press). The augmented Zagreb index, vertex connectivity and matching number of graphs. Bulletin of the Iranian Mathemat- ical Society. Ali, A., Raza, Z. & Bhatti, A. A. 2016 (in press). On the augmented Zagreb index. Kuwait Journal of Science. Dimitrov, D. 2014. On structural properties of trees with minimal atom-bond con- nectivity index. Discrete Applied Mathematics 172: 28-44. Estrada, E., Torres, L., Rodrguez, L. & Gutman, I. 1998. An atom-bond connectivity index: modelling the enthalpy of formation of alkanes. Indian Journal of Chemistry-Section A 37: 849-855. Furtula, B., Graovac, A. & Vukiˇcevi´c, D. 2010. Augmented Zagreb index. Journal of Mathematical Chemistry 48: 370-380. Gan, L., Hou, H. & Liu, B. 2011. Some results on atom-bond connectivity index of graphs. MATCH Communications in Mathematical and in Computer Chemistry 66: 669-680. Gao, J. & Lu, M. 2005. On the Randi´c index of unicyclic graphs. MATCH Commu- nications in Mathematical and in Computer Chemistry 53: 377-384. Goubko, M., Magnant, C., Nowbandegani, P. S. & Gutman, I. 2015. ABC index of trees with fixed number of leaves. MATCH Communications in Mathematical and in Computer Chemistry 74: 697-702. Gutman, I. 2013. Degree-based topological indices. Croatica Chemica Acta 86: 351- 361. Furtula, B., Gutman, I. & Elphick, C. 2014. Three new/old vertex-degree-based topological indices. MATCH Communications in Mathematical and in Computer Chem- istry 72: 617-632. Gutman, I. & Toˇsovi´c, J. 2013. Testing the quality of molecular structure descrip- tors: Vertex-degree-based topological indices. Journal of the Serbian Chemical Society 78: 805-810. Harary, F. 1969. Graph Theory. Addison-Wesley, Reading, MA. Huang, Y. & Liu, B. 2015. Ordering graphs by the augmented Zagreb indices. Jour- nal of Mathematical Research with Applications 35(2): 119-129. Manso, F. C. G., Ju´nior, H. S., Bruns, R. E., Rubira, A. F. & Muniz, E. C. 2012. Development of a new topological index for the prediction of normal boiling point temperatures of hydrocarbons: The Fi index. Journal of Molecular Liquids 165: 125-132. Palacios, J. L. 2014. A resistive upper bound for the ABC index. MATCH Commu- nications in Mathematical and in Computer Chemistry 72: 709-713. Pan, X. F., Xu, J. M. & Yang, C. 2006. On the Randi´c index of unicyclic graphs 9 with k pendant vertices. MATCH Communications in Mathematical and in Computer Chemistry 55: 409-417. Randi´c, M. 1975. On characterization of molecular branching. Journal of the Ameri- can Chemical Society 97: 6609-6615. Raza, Z., Bhatti, A. A. & Ali, A. 2015 (in press). More on comparison between first geometric-arithmetic index and atom-bond connectivity index. Miskolc Mathemat- ical Notes. Trinajsti´c, N. 1992. Chemical Graph Theory (2nd revised ed.). CRC Press, Florida. Zhan, F., Qiao, Y. & Cai, J. 2015. Unicyclic and bicyclic graphs with minimal augmented Zagreb index. Journal of Inequalities and Applications. DOI 10.1186/s13660- 015-0651-2. 10