# Extremal Values of Randić Index among Some Classes of Graphs

Authors: Ali Ghalavand; Ali Reza Ashrafi; Marzieh Pourbabaee
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

SupposeG is a simple graph with edge set EG. The Randić index RG is defined as RG=∑uv∈EG1/degGudegGv, where degGu and degGv denote the vertex degrees of u and v in G, respectively. In this paper, the first and second maximum of Randić index among all n−vertex c−cyclic graphs was computed. As a consequence, it is proved that the Randić index attains its maximum and second maximum on two classes of chemical graphs. Finally, we will present new lower and upper bounds for the Randić index of connected chemical graphs.


---

## Body

## 1. Mathematical Notions and Notations

In this section, we first describe some mathematical notions that will be kept throughout. A pairG=V,E in which V is a finite nonempty set and E is a subset of 2-elements subsets of V is called a simple graph. Throughout this paper, the term graph means simple graph and the sets V=VG and E=EG in definition of G are called the vertex set and edge set of G, respectively.SupposeG is a graph. For simplicity of our argument, an edge e=a,b in G is simply written as e=ab. Choose a vertex v in G. The vertex degree of v, degGv, is defined as the number of edges in the form ax. A chemical graph is a graph in which all vertices have degrees less than or equal to 4 [1]. The reason for this name is from quantum chemistry in which it is convenient to model a molecule M in such a way that vertices are used to denote atoms and edges are for chemical bonds.The set of all vertices adjacent to a vertexv is denoted by Nv,G and notations Δ=ΔG, ni=niG, and εi=εiG are used for the maximum degree, the number of vertices of degree i, and the number of edges of degree i in G, respectively. The number of edges connecting a vertex of degree i with a vertex of degree j in G is denoted by mi,jG. A connected n−vertex graph G is called to be c-cyclic if it has n+c−1 edges and the number c=cG is said to be the cyclomatic number of G.SupposeW is a nonempty subset of vertices in a graph G. The subgraph of G obtained by deleting the vertices of W is denoted by G−W, and similarly, if F⊆EG, then the subgraph obtained by deleting all edges in F is denoted by G−F. In the case that W=v or F=xy, the subgraphs G−W and G−F will shortly be written as G−v or G−xy, respectively. Furthermore, if x and y are nonadjacent vertices in G, then the notation G+xy is used for the graph obtained from G by adding an edge xy.The Randić index of a graphG is defined as(1)RG=∑uv∈EG1degGudegGv.This topological index was proposed by Milan Randić [2] under the name “branching index.” The Randić index is suitable for measuring the extent of branching of the carbon-atom skeleton of saturated hydrocarbons. We encourage the interested readers to consult the books [3,4] for more information on this topic.


## 2. Background Materials

This section aims to briefly review the literature on ordering graphs concerning the Randić index. By referring to Theorems 2.2 and 2.3 in [5], among all n-vertex trees, the star Sn has the minimum Randić index and the path Pn attains the maximum Randić index. Caporossi et al. [6] proved that among all 1-cyclic graphs of order n, the cycle Cn attains the maximum value, and the unicyclic graphs obtained by attaching a pendant path to a vertex of a cycle attain the second maximum Randić index. These are the starting point of the following problem.Question 1.
Findn-vertex c-cyclic graphs with maximum and minimum Randić index.
Shiu and Zhang [7] obtained the maximum value of Randić index in the class of all n−vertex chemical trees with k pendants such that n<3k−2. Shi [8] obtained some interesting results for chemical trees with respect to two generalizations of Randić index. Dehghan-Zadeh et al. [9, 10] obtained the first and second maximum of Randić index in the class of all n−vertex c-cyclic graphs when c=3,4.
Deng et al. [11] considered various degree mean rates of an edge and gave some tight bounds for the variation of the Randić index of a graph G in terms of its maximum and minimum degree mean rates over its edges. Gutman et al. in a recent interesting paper [12] investigated the connection between Randić index and the degree-based information content of molecular and also general graphs. This connection is based on the linear correlation between Randić index and the logarithm of the multiplicative version of the Randić index.
The aim of this paper is to proceed with Question 1. We will obtain the first and second maximum of Randić index among allc-cyclic graphs. This extends some results in [6, 9, 10].


## 3. Five Graph Transformations

In this section, five graph transformations will be presented which are useful in computing Randić index of graphs. The transformations I and II were introduced in [13]. (1)
Transformation I. Suppose that G is a graph with a given vertex w. In addition, we assume that P:v1,v2,…,vk and Q:u1u2…ul are two paths of lengths k−1 and l−1, respectively. Let G1 be the graph obtained from G, P, and Q by attaching edges v1w and wu1. Define G2=G1−v1w+ulv1. The above-referred graphs are illustrated in Figure 1.(2)
Transformation II. Suppose that G is a graph with given vertices x and y such that degGx,degGy≥2 and for all v∈Nx,G, degGx≥2. In addition, we assume that P:v1,v2,…,vl and Q:u1,u2,…,uk are two paths of lengths l−1 and k−1, respectively. Define G1 be the graph obtained from G, P, and Q by attaching vertices yv1, u1x, and G2=G1−u1x+vlu1. See Figure 2 for more details.(3)
Transformation III. Suppose that G is a graph with vertices x,y,w, and z such that xy,wz⊆EG. In addition, we assume that G′ is a trivial graph with vertex set v. Define G1=G−xy+xv,vy and G2=G−wz+wv,vz. The above-referred graphs are illustrated in Figure 3.(4)
Transformation IV. Suppose that G is a graph with given vertex w such that degGw=ΔG≥4, Nw,G=w1,…,wdegGw and degGw1=degGw2=2. In addition, we assume that v∈VG, degGv≥2, and vw1∈EG. Define G′=G−ww2+w1w2. See Figure 4 for more details.(5)
Transformation V. Suppose that G is a graph with vertices x1,x2,x3,x4,x5,x6, and w such that x1x2,x2x3,x2w,x4x5,x5x6⊆EG, degGx1=degGx2=degGx3=3, degGx4=4, degGx5=2, and degGx6=1 or 2. Define G′=G−x2w+x5w. The above-referred graphs are illustrated in Figure 5.Figure 1
The graphs (a)G1 and (b) G2 in Transformation I.
(a)(b)Figure 2
The graph (a)G1 and (b) G2 in Transformation II.
(a)(b)Figure 3
The graph (a)G1 and (b) G2 in Transformation III.
(a)(b)Figure 4
The graph (a)G and (b) G′ in Transformation IV.
(a)(b)Figure 5
The graph (a)G and (b) G′ in Transformation V.
(a)(b)It is well-known that if the derivativef′x of a continuous function fx satisfies f′x>0 on an open interval a,b, then fx is increasing on a,b.Lemma 1.
The following hold:(1)
LetG1 and G2 be two graphs satisfying the conditions of Transformation I. If degGw≥3 or degGw=2 and minuw∈EGdegGu≤168 or degGw=1 and minuw∈EGdegGu≤30, then RG2>RG1.(2)
LetG1 and G2 be two graphs satisfying the conditions of Transformation II and let degGx=a, Nx,G=h1,…,ha, degGhi=di, degGhi=di,1≤i≤a,di≤di+1,1≤i≤a−1. If a≥5 or a=4 and d2≤20 or a=3 and d2≤6 or a=2 and d2≤5, then RG2>RG1.(3)
LetG1 and G2 be two graphs as shown in Transformation III.(a)
IfdegGx,degGy≥3, and degGz∈1,2, then RG2>RG1(b)
IfdegGx=2, degGw≥3, and degGz=1, then RG2>RG1(c)
IfdegGx=2 and degGw=2, then RG2=RG1(4)
LetG and G′ be two graphs satisfying the conditions of Transformation IV. Then, RG′≥RG.(5)
LetG and G′ be two graphs satisfying the conditions of Transformation V. Then, RG′>RG.Proof.
(1)
Letx=degGw, Nw,G=l1,…,lx, dGli=di, 1≤i≤x, mini=1xdi=d1, and k,l≥2. Then, by definition,(2)RG2−RG1=12x+1+1+∑i=1x1dix+1−22x+2+12+∑i=1x1dix+2≥12+1d11x+1−1x+2−121x+2+1−12.Now, by Equality (2),RG2−RG1≥1/21/x+1−1/x+2+1/21/x+2+1−1/2>0.013, for x≥3, RG2−RG1≥0.0000024, for x=2 and d1≤168, and RG2−RG1≥0.000086, for x=1 and d1≤30. The proof of other cases of k and l is similar, and we omit them.(2)
LetdegGx=a, Nx,G=h1,…,ha, degGhi=di,1≤i≤a,di≤di+1,1≤i≤a−1 and k,l≥2. Then, by definition,(3)RG2−RG1=1+∑i=1a1dia−12a+1+12+∑i=1a1dia+1≥1−12a+1−12+1d1+1d21a−1a+1.And, by last equality,RG2−RG1>0.0042 for a≥5, RG2−RG1>0.00027 for a=4 and d2≤20, RG2−RG1>0.0024 for a=3 and d2≤6, and RG2−RG1>0.0007 for a=3 and d2≤5. The proof of other cases of k and l is similar, and we omit them.(3)
SupposedegGx=s, degGy=r, degGw=l, and degGz=t. To prove (a), we note that(4)RG2−RG1=1sr+12l+12t−12s+12r+1lt=1sr−12s−12r+12l−12t−1lt>−0.48+0.50>0.To prove (b), we first calculate the difference betweenRG2 and RG1.(5)RG2−RG1=12+12l−12+1l.Lethx=1/2x−1/x, for x∈0,∞. Then, h is increasing on 0,∞, and hence by equation (5), RG2−RG1>0.038. For the proof of (c), it is enough to notice that mi,jG1=mi,jG2,1≤i≤j≤n−1. Thus, RG2=RG1, as desired.(4)
Suppose thatdegGv=s, degGw=q, and degGwi=di,2≤i≤q. Then,(6)RG′−RG=13s+13q−1+16+∑i=3q1q−1di−12s+22q+∑i=3q1qdi≥26+13q−1+q−2q−1q−14+22q−q−2q2>0.02,as desired.(5) Suppose thatdegGx6=r. Then, by definition,(7)RG′−RG=29+18+12r−26+112+13r>0.0068.
Hence, the result.
For a graphG, its first Zagreb index M1G is defined as M1G=∑v∈VGdegGv2.Lemma 2 (see [14]).
IfG is a connected graph with n vertices and m edges, then(8)ε1G=4m−M1G+∑i=32n−4εiGi−2,ε2G=M1G−3m−∑i=32n−4εiGi−1.Theorem 1.
LetG be a connected graph with n≥3 vertices and m edges.(1)
IfΔG≤3 or (ΔG≤11 and m1,4G=m2,3G=0), then RG≥4m−M1G/2+M1G−3m/2. The equality holds if and only if G≅Pn.(2)
IfΔG≤3 and m2,2G=m1,4G=m2,3G=0 or (ΔG≤5 and m2,2G=m1,4G=m2,3G=m1,5G=m2,4G=m3,3G=0), then RG≥4m−M1G/2+M1G−3m/3, with equality if and only if G≅S4.Proof.
By definition,(9)RG=∑1≤i≤j≤n−1mi,j1ij≥m1,212+m1,313+m2,212+∑i=32n−4εiG1ΔG.1.
The last equality forΔG≤3 gives(10)RG≥m1,212+12m1,3+m2,2+∑i=34εiG13=12ε1G+12ε2G+∑i=34εiG13,and by Lemma2,(11)RG≥124m−M1G+∑i=34εiGi−2+12M1G−3m−∑i=34εiGi−1+∑i=34εiG13=4m−M1G2+M1G−3m2+12−12∑i=34εiGi−1−12−13∑i=34εiG≥4m−M1G2+M1G−3m2+212−12∑i=34εiG−12−13∑i=34εiG=4m−M1G2+M1G−3m2+12−1+13∑i=34εiG≥4m−M1G2+M1G−3m2.Equality holds if and only ifG≅Pn. Let ΔG≤11 and m1,4G=m2,3G=0. Then, by Equality (9),(12)RG≥m1,212+12m1,3+m2,2+∑i=420εiG111=12ε1G+12ε2G+∑i=420εiG111,and by Lemma2 and some simple calculations,(13)RG≥4m−M1G2+M1G−3m2+312−12∑i=420εiG−12−111∑i=420εiG=4m−M1G2+M1G−3m2+22−32+111∑i=420εiG≥4m−M1G2+M1G−3m2,with equality if and only ifG≅Pn.(2)
A similar argument as the case 1, it can be proved that forΔG≤3 and m2,2G=m1,4G=m2,3G=0,(14)RG≥4m−M1G2+M1G−3m3+22−33+13ε4G≥4m−M1G2+M1G−3m3,with equality if and only if G≅S4. For ΔG≤5 and m2,2G=m1,4G=m2,3G=m1,5G=m2,4G=m3,3G=0,(15)RG≥4m−M1G2+M1G−3m3+32−43+15∑i=58εiG≥4m−M1G2+M1G−3m3,with equality if and only if G≅S4. This completes the proof.Theorem 2 (see [6]).
LetG be a graph with n vertices. Then,(16)RG=n2−12∑uv∈EG1degGu−1degGv2.Lemma 3 (see [15]).
IfG is a connected graph with n vertices and cyclomatic number c, then n1G=2−2c+∑i=3ΔGi−2ni and n2G=2c+n−2−∑i=3ΔGi−1ni.Corollary 1.
LetG be a connected graph with n vertices and cyclomatic number c.(1)
Ifc=5, then n1G=∑i=3ΔGi−2ni−8 and n2G=n+8−∑i=3ΔGi−1ni(2)
Ifc=6, then n1G=∑i=3ΔGi−2ni−10 and n2G=n+10−∑i=3ΔGi−1ni
Defineϒ1n=G|n3=8,n2=n−8, ϒ2n=G|n1=1,n3=9,n2=n−10, ϒ3n=G|n3=10,n2=n−10, and ϒ4n=G|n1=1,n3=11,n2=n−12.Lemma 4.
LetG be a connected graph with n vertices, m edges, and cyclomatic number c.(1)
Supposen1=0 and 0<ni<n for some 3≤i≤n−1. Then, mi,iG≤niG−2+c.(2)
Supposen1≥1 and 0<ni<n for some 3≤i≤n−1. Then, mi,iG≤niG−1+c.Proof.
Sincen1=0, cG−v≤cG−1, for all v∈VG. Now, the proof follows from this fact that m=n−1+c. The part (2) is similar.
Letn be a positive integer. Define(17)Ω1n=G∈ϒ1n|m3,3=11,m2,3=2,m2,2=n−9,Ω2n=G∈ϒ2n|m3,3=13,m2,3=1,m1,2=1,m2,2=n−11,Ω3n=G∈ϒ3n|m3,3=14,m2,3=2,m2,2=n−11,Ω4n=G∈ϒ4n|m3,3=16,m2,3=1,m1,2=1,m2,2=n−13.
IfGi∈Ωin for 1≤i≤4, then RG1=1/2n−5−26/6, RG2=1/2n−7−6+32/6, RG3=1/2n−5−26/6, and RG4=1/2n−7−6+32/6.Theorem 3.
The following hold:(1)
LetG be a connected graph with n≥9 vertices and cyclomatic number 5. Then, RG≤1/2n−5−26/6, with equality if and only if G∈Ω1n.(2)
LetG be a connected graph with n≥11 vertices and cyclomatic number 6. Then, RG≤1/2n−5−26/6, with equality if and only if G∈Ω3n.Proof.
(1)
Ifn1G=0, then by Corollary 1 and Theorem 2, RG≤1/2n−5−26/6, with equality if and only if G∈Ω1n. For n1G=1, RG≤1/2n−7−6+32/6<1/2n−5−26/6. Let n1G≥2. Then, again by Corollary 1 and Theorem 2, RG≤1/2n−3−22/2<1/2n−5−26/6.(2)
Proof is similar to the last case, and we omit it.Remark 1.
(1)
LetG be a connected graph with n=8 vertices and cyclomatic number 5. Then, RG≤4, with equality if and only if G is a 3-regular graph.(2)
LetG be a connected graph with n=10 vertices and cyclomatic number 6. Then, RG≤5, with equality if and only if G is a 3-regular graph.
For a positive numberc≥3, we define(18)Λc1n=G|m3,3=3c−4,m2,3=2,m2,2=n−2c−1,Γc1n=G|m3,3=3c−2,m2,3=1,m1,2=1,m2,2=n−2c+1.
IfG1∈Λc1n and G2∈Γc1n, then RG1=1/2n−5−26/6 and RG2=1/2n−7−6+32/6.Proposition 1.
LetG be a connected graph with n vertices, m edges, and cyclomatic number c, where c≥3 is a positive integer. If n≥2c−1 and n1G=0, then n2G≥1.Proof.
Those are well-known thatc=m−n+1 and ∑i=1nniGi=2m. Therefore, 2c=2n2G+∑i=3nniGi−2n+2. Thus, 2c≥2n2G+3n−n2G−2n+2=n−n2G+2, and this implies that n2G≥n−2c+2. Now, since n≥2c−1, n2G≥1.
By Proposition1 and a similar argument as the proof of Theorem 3, we will have the following general result.Theorem 4.
LetG be a connected graph with n vertices and cyclomatic number c, where c≥3 is a positive integer.(1)
Ifn≥2c−1, then RG≤1/2n−5−26/6, with equality if and only if G∈Λc1n.(2)
Ifn=2c−2, then RG≤1/2n, with equality if and only if G is a 3-regular graph.
Letn be a positive number, ϒ5n=G|n1=0,n4=1,n3=6,n2=n−7 and ϒ6n=G|n1=0,n4=1,n3=8,n2=n−9. Define(19)Ω5n=G∈ϒ5n|m4,3=4,m3,3=6,m2,3=2,m2,2=n−8,Ω6n=G∈ϒ1n|m3,3=10,m2,3=4,m2,2=n−10,Ω7n=G∈ϒ6n|m4,3=4,m3,3=9,m2,3=2,m2,2=n−10,Ω8n=G∈ϒ3n|m3,3=13,m2,3=4,m2,2=n−12.
IfGi∈Ω5n for 1≤i≤4, then RG1=1/2n−6−23+6/3,RG2=1/2n−5−26/3, RG3=1/2n−6−23+6/3 and RG4=1/2n−5−26/3.Theorem 5.
The following hold:(1)
LetG be a connected graph with n≥9 vertices and cyclomatic number 5. If G∉Ω1n, then RG≤1/2n−6−23+6/3, with equality if and only if G∈Ω5n.(2)
LetG be a connected graph with n≥11 vertices and cyclomatic number 6. If G∉Ω3n, then RG≤1/2n−6−23+6/3, with equality if and only if G∈Ω7n.Proof.
(1)
Letn1G=0 and G∉Ω1n. For ΔG=3, m2,3≥4 and Corollary 1 and Theorem 2 give RG≤1/2n−5−26/3<1/2n−6−23+6/3. For ΔG≥4, RG≤1/2n−6−23+6/3, with equality if and only if G∈Ω5n. If n1G≥1, then RG≤1/2n−7−6+32/6<1/2n−6−23+6/3.(2)
Proof is similar to Case 1, and we omit it.
By a simple calculation, one can easily see that Theorem5 (1) holds for n=8 and Theorem 5 (2) holds for n=10. On the other hand, Theorems 3 and 5 imply the following result.Corollary 2.
The following hold:(1)
Supposen≥9. The connected graphs with cyclomatic number 5 in the sets Ω1n and Ω5n have the first and second maximum Randić index among all n-vertex connected graphs with cyclomatic number 5, respectively.(2)
Supposen≥11. The connected graphs with cyclomatic number 6 in the sets Ω7n and Ω8n have the first and second maximum Randić index among all n-vertex connected graphs with cyclomatic number 6, respectively.
Supposec≥4 is a positive integer. Define(20)Λc2n=G|m3,3=3c−5,m2,3=4,m2,2=n−2c,Γc2n=G|m4,3=4,m3,3=3c−9,m2,3=2,m2,2=n−2c−2.
IfH1∈Λc2n and H2∈Γc2n, then RH1=1/2n−5−26/3 and RH2=1/2n−6−23+6/3.Theorem 6.
LetG be a connected graph with n vertices and cyclomatic number c≥4.(1)
Ifn≥2c−1 and G∉Λc1n, then RG≤1/2n−6−23+6/3, with equality if and only if G∈Γc2n.(2)
Ifn=2c−2 and G is not a 3-regular graph, then RG≤1/2n−6−23+6/3, with equality if and only if G∈Γc2n.Proof.
The result follows from Proposition1 and a similar argument as Theorem 3.
We end this section with the following result that follows from Theorems4 and 6.Theorem 7.
LetG be a connected graph with n vertices and cyclomatic number c≥4.(1)
Ifn≥2c−1, then the connected graphs with cyclomatic number c in the sets Λc1n and Γc2n have the first and second maximum Randić index among all n-vertices connected graphs with cyclomatic number c, respectively.(2)
Ifn=2c−2, then the 3-regular connected graphs and the connected graphs in the set Γc2n with cyclomatic number c have the first and second maximum Randić index among all n-vertices connected graphs with cyclomatic number c, respectively.


## 4. Connected Chemical Graphs

LetG be a connected chemical graph with n vertices and m edges. By Lemma 3,(21)n1=2n−2m+n3+2n4,n2=2m−n−2n3−3n4,and by Lemma 2,(22)ε1G=4m−n1+4n2+9n3+16n4+ε3G+2ε4G+3ε5G+4ε6G,ε2G=n1+4n2+9n3+16n4−3m−2ε3G+3ε4G+4ε5G+5ε6G.Now, by some calculations, we have(23)ε1G=2n−2m−2n3−6n4+ε3G+2ε4G+3ε5G+4ε6G,ε2G=3m−2n+2n3+6n4−2ε3G+3ε4G+4ε5G+5ε6G.SupposeMk=mi,j|1≤i≤j≤4andi+j=k+2, 1≤k≤4. Since εk=∑x∈Mkx,1≤k≤4,(24)m1,2=2n−2m−2n3−6n4+m1,4+m2,3+2m2,4+2m3,3+3m3,4+4m4,4,m2,2=3m−2n+2n3+6n4−m1,3+2m1,4+2m2,3+3m2,4+3m3,3+4m3,4+5m4,4,and since m1,3=3n3−m2,3−2m3,3−m3,4 and m1,4=4n4−m2,4−m3,4−2m4,4,(25)m1,2=2n−2m−2n3−2n4+m2,3+m2,4+2m3,3+2m3,4+2m4,4,(26)m2,2=3m−2n−n3−2n4−m2,3−m2,4−m3,3−m3,4−m4,4.On the other hand,(27)RG=12m1,2+13m1,3+12m1,4+12m2,2+16m2,3+18m2,4+13m3,3+112m3,4+14m4,4.By equations (25)–(27), we have(28)RG=123−22m+22n+2n−121−23+22n3−2−1n4+1632+32−23−3m2,3+1432−4m2,4+1662−43−1m3,3+1662−3−6m3,4+1442−5m4,4.Theorem 8.
LetG be a connected chemical graph with n>5 vertices and m edges. Then,(1)
RG≤1/23−22m+22n+2n, with equality if and only if G≅Pn or Cn(2)
RG≥1/622−332+23−32−3n−32−23+32−3m+3Proof.
It is easy to see thatn3≥1/3m2,3+2m3,3+m3,4 and n4≥1/4m2,4+m3,4+2m4,4. Therefore, by equation (28), we have(29)RG≤123−22m+22n+2n−164−32−2m2,3−143−22m2,4−163−22m3,3−11211−23−52m3,4−143−22m4,4≤123−22m+22n+2n,with equality if and only if G≅Pn or Cn. On the other hand, n3+n4≤n and m2,3+m2,4+m3,3+m3,4+m4,4≥n3+n4−1. Therefore, by equation (28),(30)RG≥123−22m+22n+2n−2−1n3+n4+1632+32−23−3n3+n4−1≥123−22m+22n+2n−1632+23−3−32n3+n4+5−232≥1622−332+23−32−3n−32−23+32−3m+3.
This completes the proof.



---

*Source: 7758172-2021-06-14.xml*