# New Bounds for the Randić Index of Graphs

Authors: Maryam Atapour; Akbar Jahanbani; Rana Khoeilar
Journal: Journal of Mathematics
 (2021)

---

## Abstract

The Randić index of a graphG is defined as the sum of weights 1/dudv over all edges uv of G, where du and dv are the degrees of the vertices u and v in G, respectively. In this paper, we will obtain lower and upper bounds for the Randić index in terms of size, maximum degree, and minimum degree. Moreover, we obtain a generally lower and a general upper bound for the Randić index.


---

## Body

## 1. Introduction

LetG be a simple graph with a vertex set V=VG and edge set EG. The integers n=nG=VG and m=mG=EG are the order and the size of the graph G, respectively. The open neighborhood of vertex v is NGv=Nv=u∈VG|uv∈EG, and the degree of v is dGv=dv=Nv. One of the most active fields of research in contemporary chemical graph theory is the study of topological indices of graph invariants that can be used for describing and predicting physicochemical and pharmacologic properties of organic compounds. Topological indices have been used and have been shown to give a high degree of predictability of pharmaceutical properties. In 1947, Wiener [1] conceived the first molecular graph-based structure descriptor, eventually named the “Wiener index.” The information on the chemical constitution of the molecule is conventionally represented by a molecular graph. Graph theory was successfully provided by the chemist with a variety of very useful tools, namely, topological indices. Among the several hundred presently existing graph-based molecular structure descriptors [2], the Randić index RG of a graph was introduced by the chemist Randić under the name of “branching index” in 1975 [3] as the sum of(1)RG=∑uv∈EG1dudv.Also, it was designed in 1975 to measure the extent of branching of the carbon-atom skeleton of saturated hydrocarbons. It was demonstrated that the Randić index is well correlated with a variety of physicochemical properties of alkanes, such as boiling point, enthalpy of formation, surface area, and solubility in water.The Randić index is certainly the most widely applied in chemistry and pharmacology, in particular for designing quantitative structure-property and structure-activity relations. Randić proposed this index to “quantitatively characterize the degree of molecular branching.” According to him, “the degree of branching of the molecular skeleton is a critical factor” for some molecular properties such as “boiling points of hydrocarbons and the retention volumes and the retention times obtained from chromatographic studies” (all citations are taken from [3]).Zhou et al. [4] obtained lower and upper bounds for the general Randić index, and Du et al. [5] obtained new lower and upper bounds for the Randić index in terms of other topology indices; for other bounds, see [6, 7]. Then, in this paper, we will obtain new lower and upper bounds for the Randić index.


## 2. Main Results

In this section, we present lower and upper bounds for the Randić index.We make use of the following lemmas in this paper to obtain the results.Lemma 1 (see [8]).
Letxi and yi,i=1,…,n, be real numbers such that Xxi≤yi≤Yxi for each i=1,…,n. Then,(2)X+Y∑i=1nxiyi≥∑i=1nyi2+XY∑i=1nxi2,with equality holding if and only if either yi=Xxi or yi=Yai for each i=1,…,n.Lemma 2 (see [9]).
Lets1,s2,…,sn be nonnegative real numbers with the property(3)s1+s2+⋯+sn=1.
Further, let(4)b1≥b2≥…≥bn,be real numbers, and assume that there are t,T∈R such that 0<t≤bi≤T<+∞ for each i,i=1,2,…,n. Then,(5)∑i=1nsibi+tT∑i=1nsibi≤t+T.Equality in equation (5) is obtained if and only if T=b1=⋯=bk≥bk+1=⋯=bn=t for some k,1≤k≤n.Theorem 1.
LetG be a connected graph of size m, maximum degree Δ, and minimum degree δ. Then,(6)RG≥Δ3δ3R−2G+M2GΔ3+δ3,and the equality holds in (6) if and only if G is a regular graph.Proof.
By the definition of the Randić index, we can write(7)RG=∑vivj∈EG1didj=∑vivj∈EGdidj×1didj.
For each edgevivj∈EG, it holds that(8)δ3didj≤didj≤Δ3didj,where the left-hand side equality is attained if and only if di=dj=δ for vivj∈EG and the right-hand side equality is attained if and only if di=dj=Δ for vivj∈EG.
Settingxi=1/didj,yi=didj,X=δ3, and Y=Δ3 in Lemma 1 and Inequality (8), we have(9)RG=∑vivj∈EGdidj×1didj=1Δ3+δ3Δ3+δ3∑vivj∈EGdidj×1didj≥1Δ3+δ3Δ3δ3∑vivj∈EG1didj2+∑vivj∈EGdidj=Δ3δ3R−2G+M2GΔ3+δ3,and the proof is completed.
Suppose that equality holds in (6). Then, the equality holds in (8). From the equality in (8), by Lemma 1, we obtain(10)didj=δ3didj,or(11)didj=Δ3didj,for each edge vivj∈EG. By the equality condition in (9), we must have di=dj=δ or di=dj=Δ for each edge vivj∈EG, i.e., G is regular as G is connected.
Conversely, one can easily see that equality holds in (6) for regular graph.
For any nontrivial connected graphG, R−2G≥m/Δ4 and M2G≥mδ2 with either equality if and only if G is regular. From Theorem 1, it then follows immediately the following consequence.Corollary 1.
LetG be a connected graph of size m, maximum degree Δ, and minimum degree δ. Then,(12)RG≥mδ2ΔΔ2−Δδ+δ2.Next, we present an upper bound for the Randić index in terms of sizem, maximum degree Δ, and minimum degree δ.Theorem 2.
LetG be a graph of size m, with maximum degree Δ and minimum degree δ. Then, the following equality holds:(13)RG≤mδ2Δ+δ3+mΔδΔ+δ, if and only if G≅K2.Proof.
Note that for each edgevivj∈EG, we have δ≤didj≤Δ and 1/didj≤δ; hence, we can write that(14)1didj−Δ1didj−δ≥0.
By Inequality (13), we have(15)1didj+Δδ≥Δ+δdidj.
Therefore, by definition of the Randić index and Inequality (15), we have(16)Δ+δRG=∑vivj∈EGΔ+δdidj≤∑vivj∈EG1didj+∑vivj∈EGΔδ≤mδ2+mΔδ.and this leads to the desired bound.
Suppose that equality holds in (13). Then, the equality holds in (14). From the equality in (14), we have(17)1didj=Δ,or(18)1didj=δ.
Note thatΔ and δ are natural numbers; hence, we have di=dj=1, for each edge vivj∈EG, i.e., G≅K2.
Conversely, one can easily see that equality holds in (13) for G≅K2.
Now, we present a lower bound for the Randić index in terms of sizem, maximum degree Δ, and minimum degree δ.Theorem 3.
LetG be a graph of size m, with maximum degree Δ and minimum degree δ. Then, the following inequality holds:(19)RG≥mδδΔ+Δ2+mΔ+δ,if and only if G is a regular graph.Proof.
Note that for each edgevivj∈EG, we have 1/Δ≤1/didj≤1/δ; hence, we can write that(20)1didj−1Δ1didj−1δ≤0.
By Inequality (20), we have(21)1didj+1Δδ≤Δ+δΔδ1didj.
Therefore, by definition of the Randić index and Inequality (21), we have(22)Δ+δΔδRG=Δ+δΔδ∑vivj∈EG1didj≥∑vivj∈EG1didj+∑vivj∈EG1Δδ≥mΔ2+mΔδ,and this leads to the desired bound.
Suppose that equality holds in (19). Then, the equality holds in (20). From the equality in (20), we have(23)1didj=1Δ,or(24)1didj=1δ.
By the equalities condition in (23) and (24), we must have di=dj=δ or di=dj=Δ for each edge vivj∈EG, i.e., G is the regular graph.
Conversely, one can easily see that equality holds in (19) for regular graph.
Here, we present a lower bound for the Randić index in terms of sizem, maximum degree Δ, and minimum degree δ.Theorem 4.
LetG be a graph of size m, with maximum degree Δ and minimum degree δ. Then, the following equality holds:(25)RG≥m2Δ2−δ2,if and only if G is a regular graph.Proof.
Since for anyx,y∈R+, we have(26)x2−xy+y2≥xy.
By the definition of the Randić index and settingx=diandy=dj in Inequality (26), we can write that(27)RG=∑vivj∈EG1didj≥∑vivj∈EG1di2−didj+dj2≥∑vivj∈EG1Δ2−didj+Δ2≥∑vivj∈EG1Δ2−δ2+Δ2=m2Δ2−δ2,as desired.
Suppose that equality holds in (25). Then, the equality holds in (26). From the equality in (26), we have(28)x2−xy+y2=xy,or(29)x2+y2=2xy⟶x−y2=0.
Note thatx,y>0; hence, we get x=y; therefore, di=dj for each edge vivj∈EG.
Also, suppose that equality holds in (25). Then, the equality holds in (27). From the equality in (27), we have(30)1didj=1di2−didj+dj2,or(31)didj=di2−didj+dj2.
By equality (31),(32)2didj=di2+dj2.
Therefore,di=dj for each edge vivj∈EG.
Conversely, one can easily see that equality holds in (25) for regular graph.
For any real numberα, the general Randić index, Rα, is defined in [10] as(33)M2α=Rα=RαG=∑uv∈EGdudvα.
The concept of the first general Zagreb index introduced by Li et al. [11] is defined as(34)MαG=∑u∈VGdGαu=∑uv∈EGdGα−1u+dGα−1v,where α∈R.
In [12], the following upper bounds for ID were also established:(35)IDG≤Δα+δα2n24M1αGΔδα,ifα≥1,(36)IDG≤Δα+δα2n24M1αGΔαδ,ifα≤1,(37)IDG≤M1αGΔα+1,ifα≤−1,(38)IDG≤M1αGδα+1,ifα≥−1,(39)IDG≤M2αG+mΔ2αΔ2α+2,ifα≤−2,(40)IDG≤M2αG+mδ2αδ2α+2,ifα≥−2.
We need the following lemma to prove the next theorem.Lemma 3 (see [13]).
LetG be an undirected, simple graph of order n≥2 with no isolated vertices. Then,(41)R−1G≤12∑i=1n1di.Equality holds if and only ifG is a k-regular graph, 1≤k≤n−1.Applying Inequalities (35)–(40), we establish upper bounds for the Randić index in terms of the general first and second Zagreb indices maximum degree Δ and minimum degree δ.Theorem 5.
LetG be a graph of order n, size m, maximum degree Δ, minimal degree δ, and with no isolated vertices. Then,(42)RG≤Δα+δα2n28M1αGδα,ifα≥1,(43)RG≤Δα+δα2n28M1αGΔα−1δ,ifα≤1,(44)RG≤M1αG2Δα,ifα≤−1,(45)RG≤ΔM1αG2δα+1,ifα≥−1,(46)RG≤M2αG+mΔ2α2Δ2α+1,ifα≤−2,(47)RG≤ΔM2αG+mδ2α2δ2α+2,ifα≥−2.Proof.
By the definition of the Randić index, we can write(48)RG=∑vivj∈EG1didj=∑vivj∈EGdidj×1didj≤Δ∑vivj∈EG1didj=ΔR−1G.
By Lemma3, we have(49)RG≤Δ2∑i=1n1di,and from (35)–(40) and (49), we arrive at (42)–(47) directly.
Here, we obtain the upper bound for the inverse degree index that helps us to obtain next result.Lemma 4.
LetG be a simple graph of order n≥2, with m edges and with no isolated vertices. Then, the following equality holds:(50)∑i=1n1di≤nΔ+δ−2mΔδ,if and only if G is a k-regular graph, 1≤k≤n−1.Proof.
Settingsi=1/n and bi=di for i=1,2,…,n, t=δ and T=Δ, Inequality (5) becomes(51)1n∑i=1ndi+Δδn∑i=1n1di≤Δ+δ.
Note that(52)∑i=1ndi=2m.
Therefore, we have(53)∑i=1n1di≤nΔ+δ−2mΔδ.
Suppose that equality holds in (50). Then, the equality holds in (51). Equality in (51) holds if and only if d1=⋯=dk and dk+1=⋯=dn.
By Inequality (49) and Lemma 3, we get the next result.Corollary 2.
. LetG be a graph of order n, size m, maximum degree Δ, and minimal degree δ. Then,(54)RG≤nΔ+δ−2m2δ.
In [4], the following upper bounds for R−1 were also established:(55)R−1G≤n2Δ2+δ216mΔ2δ2,(56)R−1G≤m2Δ2+δ2dΔ2δ2,where(57)d=2m2−n−1mΔ+Δ−122m2mn+1−2mn1+2mnn.R−1G≤m2Δ2+δ2cΔ2δ2,where(58)c=2m2−n−1mΔ+Δ−12Δ2+δ2+2m−Δ−δ2n−2.
By using Inequality (48) and Inequalities (55)–(57), we get the next results.Corollary 3.
LetG be an undirected, simple graph of order n, size m, maximum degree Δ, and minimal degree δ. Then,(59)RG≤n2Δ2+δ216mΔδ2,RG≤m2Δ2+δ2dΔδ2,RG≤m2Δ2+δ2cΔδ2.Denote byA the adjacency matrix of the graph G and by D the diagonal matrix of its vertex degrees. The eigenvalues adjacency matrix is(60)λ1≥λ2≥⋯≥λn.The energy of graphG is defined as(61)EAG=∑i=1nλi.This concept was introduced by Gutman and is intensively studied in chemistry since it can be used to approximate the totalπ-electron energy of a molecule (see, e.g., [14, 15]).The normalized Laplacian matrix of a graphG is denoted by L and L=I−D−1/2AD−1/2. Its eigenvalues(62)ρ1≥ρ2≥⋯≥ρn=0,are normalized Laplacian eigenvalues of graph G. The normalized Laplacian energy (or L-energy) of a graph G is(63)ELG=∑i=1nρi−1.In [16], the following upper bounds for R−1 were also established:(64)R−1G≤ELG2,(65)ELG≤EAGδ.Applying Inequalities (48), (64), and (65), we establish upper bounds for the Randić index in terms of the energy and the normalized Laplacian energy.Corollary 4.
LetG be a graph with maximum degree Δ and minimum degree δ. Then,(66)RG≤ΔELG2,RG≤ΔEAG2δ.In [17], the following lower bounds for R−1 were also established:(67)R−1G≥n2n−1+14ρ1−ρn−12.Theorem 6.
LetG be graph of order n and minimal degree δ. Then,(68)RG≥δn2n−1+δ4ρ1−ρn−12.Equality holds if and only ifG≅Kn.Proof.
By the definition of the Randić index and by Inequality (67), we can write(69)RG=∑vivj∈EG1didj=∑vivj∈EGdidj×1didj≥δ∑vivj∈EG1didj(70)=δR−1G≥δn2n−1+δ4ρ1−ρn−12,and the proof is completed.
Suppose that equality holds in (68). Then, the equality holds in (69) and (70). From the equality in (69), we have di=dj=δ for each edge vivj∈EG. From the equality in (70), we have G≅Kn.
Conversely, one can easily see that equality holds in (68) for graph Kn.
Denote(71)ΛG=TG|is a topology index of graphG,(72)ΩG=TG|Tis a topology index of graphGandTG≥RG,where RG is the Randić index.
Next, we present a general upper bound for the Randić index in terms of other topological indices.Theorem 7.
LetG be a graph with the Randić index R (G). Then, the following equality holds:(73)RG≤4ΛGΩG+ΩG−ΛG2+ΩG−ΛG2,if and only if G≅K¯n.Proof.
Forx,y,z≥0 and x≤z, we have(74)x+yz−x≥0,and by solving this inequality, we get(75)x≤4yz+z−y2+z−y2orx≥−4yz+z−y2+z−y2.
By settingx=RG,y=ΛG, and z=ΩG in Inequality (75), we obtain(76)RG≤4ΛGΩG+ΩG−ΛG2+ΩG−ΛG2.
Suppose that equality holds in (73). Then, the equality holds in (74); hence, we have(77)x+yz−x=0.
By the equality condition in (77), we obtain(78)x+y=0orz−x=0.
Therefore, we have two following cases:Case 1. If x+y=0, note that x,y≥0; hence, we obtain x=y=0.Case 2. If z−x=0, then we obtain x=z; by this fact and by Inequality (75), we get x=z=0. Since x=RG,y=ΛG, and z=ΩG, therefore, we have G≅K¯n.Conversely, one can easily see that equality holds in (73) for G≅K¯n.
DenoteΨG=TG|Tis a topology index of graphGandTG≤RG, where RG is the Randić index.
Forx,y,z≥0 and x≥z, we have(79)x+yz−x≤0.
Next, we present a general lower bound for the Randić index in terms of other topological indices.
By Inequality (79) and similarly with proof of Theorem 7, we get the next result.Theorem 8.
LetG be a graph with the Randić index R (G). Then,(80)RG≥4ΛGΨG+ΨG−ΛG2+ΨG−ΛG2.Here, we recall some of the topological indices that will need to explain one of the applications of Theorems7 and 8.The first and second Zagreb indices are vertex-degree-based graph invariants defined as(81)M1=M1G=∑uv∈EGdu+dv,M2=M2G=∑uv∈EGdudv.The quantityM1 was first considered in 1972 [18], whereas M2 in 1975 [19].The forgotten topological index has been introduced by Furtula and Gutman [20] as(82)FG=∑uv∈EGdu2+dv2.The harmonic index, denoted byHG, was defined in [21] as(83)HG=∑uv∈EG2du+dv.The (first) geometric-arithmetic index of a graph was defined in [22] as(84)GAG=∑uv∈EG2dudvdu+dv.


## 3. Applications of Theorems7 and 8

Using Theorems7 and 8, we can obtain many upper and lower bounds for the Randić index in terms of other topological indices. For example, by Theorem 7, we can obtain following upper bounds.Note that forx,y≥0, we have(85)1xy≤xy,(86)1xy≤xy,(87)1xy≤x+y2.By Inequalities (85)–(87) and definitions of topological indices, we have(88)RG≤R1G,RG≤M2G,RG≤M1G2≤M1G,and hence R1G,M1G,M2G∈ΩG. Here, we let FG,GAG,HG∈ΛG; therefore, by Theorem 7, we get the following results:(89)RG≤4R1GFG+R1G−FG2+R1G−FG2,RG≤4M2GGAG+M2G−GAG2+M2G−GAG2,RG≤4HGM1G+M1G−HG2+M1G−HG2,RG≤4M2GFG+M2G−FG2+M2G−FG2,RG≤4M1GGAG+M1G−GAG2+M1G−GAG2.Analogously above, we can obtain lower bounds for the Randić index by using Theorem8.



---

*Source: 9938406-2021-08-13.xml*