# On the Graphs of Minimum Degree At Least 3 Having Minimum Sum-Connectivity Index

Authors: Wael W. Mohammed; Shahzad Ahmed; Zahid Raza; Jia-Bao Liu; Farooq Ahmad; Elsayed M. Elsayed
Journal: Journal of Mathematics
 (2022)

---

## Abstract

For a graphG, its sum-connectivity index is denoted by χG and is defined as the sum of the numbers du+dv−1/2 over all edges uv of G, where dw denotes the degree of a vertex w∈VG. In this study, we find a sharp lower bound on the sum-connectivity index of graphs having minimum degree of at least 3 under certain constraints and characterize the corresponding extremal graphs.


---

## Body

## 1. Introduction

In chemical graph theory, graph invariants are usually known as topological indices. Such indices play an important role in the study of quantitative structure property relationship (QSPR) and quantitative structure activity relationship (QSAR). Information about several good studied topological indices can be found in [1–7] and related references listed therein.The well-known Randić-connectivity index (also known as the product-connectivity index), proposed by Randić [8] in 1975, is the most used topological index in QSPR and QSAR, which is defined as [8](1)RG=∑uv∈EGdudv−1/2.The sum-connectivity index, a variant of the product-connectivity index, of a graphG is defined as [9](2)χG=∑uv∈EGdu+dv−1/2.In the previous studies [10–12], the sum-connectivity index of several graphs of molecules was calculated. In [13], relation between the sum-connectivity index and average distance was established. Extremal results concerning minimum sum-connectivity index and matching number were obtained in [14] for trees and connected unicyclic graphs, in [15] for connected bicyclic graphs, and in [16] for cacti. Results on trees with given matching number and maximum sum-connectivity index were found in [17]. Some mathematical aspects of χ index were studied in [9], particularly for the family of trees, which contains molecular trees representing acyclic hydrocarbons. More detail about the χ index can be found in the recent survey [18] and recent articles [19, 20]. In the present study, we obtained the minimum general sum-connectivity index from the family of all n-vertex (where n≥23) graphs having minimum degree of at least 3 under certain constraints.


## 2. Main Results

Theorem 1.
Forn≥23, let G be an n-vertex graph with minimum degree of at least 3, such that G satisfies the following two conditions:(i)
IfG has a pair of adjacent vertices of degree 3, then this pair of adjacent vertices has at most one common neighbor(ii)
IfG contains no pair of adjacent vertices of degree 3, then G has a vertex of degree 3 whose all neighbors form a triangle
Then, it holds that(3)χG≥3n−3n+2+32n−1,with the equality sign if and only if G≅K3+K¯n−3.


## 3. Some Preliminaries Lemmas

In this section, some lemmas are given, which play a vital role in proving the main result.Lemma 1.
(See [21]). If e∈EG is of maximal weight, then χG>χG−e.Lemma 2.
Ifx,y,z,w≥3, then the function f defined by(4)fx,y,z,w=1x+3+1y+3+1z+3+1w+3−1x+4−1y+4−1z+4−1w+4,is strictly decreasing in all x,y,z, and w on the interval 3,∞.Proof.
(5)∂f∂x=−12x+33+12x+43<0,shows that the function f is strictly decreasing in x. Because of the symmetry, we also conclude that f is strictly decreasing in y,z, and w.Lemma 3.
Ifn is an integer greater than 16, then the function f defined by(6)fn=3n−8n+1−3n−3n+2+32n−2−32n−1+16,is positive valued.Proof.
Clearly,(7)3n−5n+1−3n−5n+2>0.
Also,(8)32n−4−32n−2>0.
So,(9)−3n+1+16>0,for all n>53.
From the above inequalities, we get thatfn>0 for all n>53.
If17≤n≤53, then fn>0 by using Mathematica. Hence, fn>0 for all n≥17.
This completes the proof of the lemma.Lemma 4.
Ifn is an integer greater than 22, then the function f defined by(10)fx=1x+3−2x+4+x−1x+n−4−x−1x+n−3,wherex≥3,is strictly increasing on the interval 3,∞.Proof.
(11)dfdx=−12x+33+1x+43+x+2n−72x+n−43−x+2n−52x+n−33.
Forx≥3, it holds that(12)763/2<22,which together with inequality 1+1/x+3≤7/6 imply that(13)1+1x+33/2≤763/2<2,which further implies that(14)2x+43/2−1x+33/2>0or1x+43/2−12x+33/2>0.
Let(15)gn=x+2n−72x+n−43,then,(16)dgdn=−2n+x+54x+n−45<0,this shows that the function g is decreasing in n.
So,(17)x+2n−72x+n−43−x+2n−52x+n−33>0.
Using these inequalities in the above equation, we get(18)dfdx>0.
Hence, the functionf is strictly increasing in x.Lemma 5.
Let(19)fn=3n−4n+1−3n−3n+2+32n−2−32n−1+2n−1−2n+36−27.
Ifn is an integer greater than 13, then fn>0.Proof.
Given,(20)fn=3n−4n+1−3n−3n+2+32n−2−32n−1+2n−1−2n+36−27>3n−4n+1−3n−3n+2+32n−2−32n−1+2n−1−2n+16.
As(21)3n−3n+1−3n−3n+2>0,32n−2−32n−1>0,also(22)2n−1−2n>0,the expression is(23)−3n+1+16>0,for all n>53.
From the above inequalities, we get thatfn>0 for all n>53.
If14≤n≤53, then fn>0 by using Mathematica. Hence, fn>0 for all n≥14.Lemma 6.
Ifn is an integer greater than 22, then the function f defined by(24)fx=1x+3−2x+4+x−1x+n−3−x−1x+n−2,wherex≥3,is strictly increasing on the interval 3,∞.Proof.
(25)dfdx=−12x+33+1x+43+x+2n−52x+n−33−x+2n−32x+n−23.
Forx≥3, it holds that(26)763/2<22,which together with inequality 1+1/x+3≤7/6 imply that(27)1+1x+33/2≤763/2<2,which further implies that(28)2x+43/2−1x+33/2>0or1x+43/2−12x+33/2>0.
Let(29)gn=x+2n−52x+n−33.
Then,(30)dgdn=x−2n+34x+n−35<0.
So,(31)x+2n−52x+n−33−x+2n−32x+n−23>0.
Using these inequalities in the above equation, we get(32)dfdx>0.
Hence, the functionf is strictly increasing in x.Lemma 7.
The functionf defined is by(33)fn=3n−14n+1−3n−3n+2+32n−2−32n−1+2n+36−27.
Ifn is an integer greater than 13, then fn is positive valued.Proof.
Given,(34)fn=3n−14n+1−3n−3n+2+32n−2−32n−1+2n+36−27>3n−14n+1−3n−3n+2+32n−2−32n−1+2n+16.
As(35)3n−3n+1−3n−3n+2>0,32n−2−32n−1>0,also(36)2n−2n+1>0,so,(37)−3n+1+16>0,for all n>53.
From the above inequalities, we get thatfn>0 for all n>53.
If14≤n≤53, then fn>0 by using Mathematica. Hence, fn>0 for all n≥14.Lemma 8.
Ifx≥3,y≥4, then the function f defined by(38)fx,y=1x+y−1x+y−1+y−1y+3−y−2y+2,is strictly increasing in x and strictly decreasing in y.Proof.
(39)∂f∂x=−12x+y3+12x+y−13>0.
Now,(40)∂f∂y=y+72y+33−y+62y+23+1x+y−13−12x+y3,∂2f∂x∂y=−34x+y−15+34x+y5<0.
So, we have(41)∂f∂y≤∂f3,y∂y=y+62y+33−y+52y+23.
Let(42)gy=y+62y+33.
Then,(43)dgdy=−y−124y+35<0,which shows that g is strictly decreasing in y.
So,(44)y+62y+33−y+52y+23<0.
By using this inequality in the above expression, we get(45)∂f∂y<0.
Hence, the functionf is strictly decreasing in y.Lemma 9.
Let(46)fn=2n−5n+1−2n−4n+2+32n−2−32n−1+16.
Ifn is an integer greater than 9, then fn>0.Proof.
As(47)2n−4n+1−2n−4n+2>0,32n−2−32n−1>0,so,(48)−2n+1+16>0,for all n>23.
From the above inequalities, we get thatfn>0 for all n>23.
If10≤n≤23, then fn>0 by using Mathematica.
Hence,fn>0 for all n≥10.Lemma 10.
Ifx≥4, then the function f defined by(49)fx=xx+3−x−1x+2,is strictly decreasing on the interval 4,∞.Proof.
(50)dfdx=x+62x+33−x+52x+23.
Let(51)gx=x+62x+33.
Then,(52)g′x=−x−124x+35<0.
So,(53)x+62x+33−x+52x+23<0.
Using this in the above equation, we get(54)dfdx<0.
Hence, the functionf is strictly decreasing in x.Lemma 11.
Ifn is an integer greater than 9, then the function f defined by(55)fn=4n−14n+1−3n−3n+2+32n−2−32n−1−n−3n+16,is positive valued.Proof.
As(56)3n−3n+1−3n−3n+2>0,32n−2−32n−1>0,the expression is(57)n−2n+1−n−3n=n+1−n+3n−3n+1>0.
So,(58)−3n+1+16>0,for all n>53.
From the above inequalities, we get thatfn>0 for all n>53.
If10≤n≤53, then fn>0 by using Mathematica.
Hence,fn>0 for all n≥10.Lemma 12.
Ifx,y,z≥4, then the function f defined by(59)fx,y,z=x−2x+3−x−3x+2+1x+y−1x+y−2+y−2y+3−y−3y+2+1y+z−1y+z−2+z−2z+3−z−3z+2+1x+z−1x+z−2,is decreasing in all x,y and z.Proof.
(60)∂f∂x=x+82x+33−x+72x+23−12x+y3−12x+z3+12x+y−23+12x+z−23,which implies(61)∂2f∂x∂y=34x+y5−34x+y−25<0,∂2f∂x∂z=34x+z5−34x+z−25<0.
Since∂2f/∂x∂y<0 and ∂2f/∂x∂z<0, it holds that(62)∂f∂x≤∂fx,4,4∂x=x+82x+35−x+52x+25−1x+43.
Let(63)Fx=x+82x+33−x+52x+23−1x+43,where x≥4. We note that(64)Fx=hx+1−hx+gx−gx+1,where(65)hx=x+52x+23,gx=1x+33.
The functionsh and g are continuous as well as differentiable on the closed interval xo,xo+1 for every fixed number xo≥4.
By virtue of Cauchy’s mean value theorem, we observe that for everyxo, there exists a number cxo∈xo,xo+1, such that(66)hxo+1−hxogxo+1−gxo=h′cxog′cxo=cxo+3cxo+25/2cxo+116,which is greater than one, and hence,(67)Fxo=hxo+1−hxo+gxo−gxo+1<0,because the function g is decreasing.
Therefore, for allx≥4, the function Fx is negative valued. Using Fx<0 in the above equation, we get(68)∂f∂x<0.
This shows that the functionf is decreasing in x.
By symmetry, it follows that(69)∂f∂y<0,∂f∂z<0,which means that the function f is decreasing in y and z. Hence, the function f is decreasing in x, y, and z.


## 4. Proof of Theorem1

Proof.
We will prove the result by induction onn. For n=23, by using the AutoGraphiX system [22], we find that K3+K¯n−3 has the maximum χ value among all n-vertex graphs having a minimum degree of at least 3, which implies that the result is true for n=23. Now, we suppose that the theorem holds for all those k-vertex graphs which satisfy all the constraints of the theorem, where 23≤k≤n−1.
If minimum degree ofG is at least 4, then we take v1v2∈EG, such that dv1+dv2≤du+dv for all uv∈EG. Clearly, the graph G−v1v2 has minimum degree of at least 3, and from Lemma 1, it follows that χG>χG−v1v2. Hence, it is sufficient to assume that the minimum degree of G is 3. Next, we consider all possible cases.Case 1:G contains at least one pair of adjacent vertices having degree 3 without common neighborsLetu1,u2∈VG be two adjacent vertices having degree 3 without any common neighbor. Let v1 and v2 be the neighbors of u1 different from u2, and w1, w2 be the neighbors of u2 different from u1. In this case, the vertex degrees dv1,dv2,dw1, and dw2 satisfy the inequality 3≤dv1,dv2,dw1,dw2≤n−2. By setting G1≅G−u1+u2v1,u2v2 and then by using Lemma 2, the inductive hypothesis, and Lemma 3, we have(70)χG=χG1+1du1+du2+1du1+dv1+1du1+dv2+1du2+dw1−1du2+1+dw1+1du2+dw2−1du2+1+dw2−1du2+1+dv1−1du2+1+dv2=χG1+16+13+dv1+13+dv2+13+dw1−14+dw1+13+dw2−14+dw2−14+dv1−14+dv2≥3n−4n+1+32n−2+4n+1−4n+2+16>3n−3n+2+32n−1.Case 2:G contains at least one pair of adjacent vertices of degree 3 with a common neighborLetu1,u2∈VG be two adjacent vertices of degree 3 having a common neighbor v. Let v1 be the neighbor of u1 different from u2, and v and w1 be the neighbors of u2 different from u1, v.Subcase i:Letdv=3, and there is an edge between v1 and v. Clearly, it holds that 3≤dv1≤n−2 and 3≤dw1≤n−3. If we take G2≅G−u1+u2v1,w1v, then by using Lemma 4, the inductive hypothesis, and Lemma 5, we get(71)χG=χG2+1du1+du2+1du1+dv+1du1+dv1−1du2+dv1−1dv+dw1+1+1du2+dw1−1du2+dw1+1+∑z∈Nw1∖u21dz+dw1−1dz+dw1+1≥χG2+26−13+dw1+1+13+dw1−13+dw1+1+dw1−1n−4+dw1−dw1−1n−4+dw1+1≥χG2+2n−1−2n+36−27≥3n−4n+1+32n−2+2n−1−2n+36−27>3n−3n+2+32n−1.Subcase ii:Letdv=3, and there is an no edge between v1 and v. Clearly, it holds that 3≤dv1≤n−3. If G3≅G−u1+u2v1,v1v, then by using Lemma 6, the induction hypothesis, and Lemma 7, we obtained(72)χG=χG3+1du1+du2+1du1+dv+1du1+dv1−1du2+dv1+1−1dv+dv1+1+∑z∈Nv1∖u11dz+dv1−1dz+dv1+1≥χG3+26+13+dv1−13+dv1+1−13+dv1+1+dv1−1n−3+dv1−dv1−1n−3+dv1+1≥χG3+2n−2n+1+36−27≥3n−4n+1+32n−2+2n−2n+1+36−27>3n−3n+2+32n−1.Subcase iii:Letdv≥4, and there is an edge between v1 and v. Clearly, it holds that 3≤dv1≤n−2. If we take G4≅G−u1+u2v1, then by using Lemma 8, the inductive hypothesis, and Lemma 9, we have(73)χG=χG4+1du1+du2+1du1+dv+1du1+dv1−1du2+dv1+1du2+dv−1du2+dv−1+1dv1+dv−1dv1+dv−1+∑z∈Nv\u1,v1,v21dv+dz−1dv−1+dz≥χG4+16+23+dv−13+dv−1+1dv1+dv−1dv1+dv−1+dv−3dv+dz+dv−3dv−1+dz≥χG4+n−1n+2−n−2n+1+16≥3n−4n+1+32n−2+n−1n+2−n−2n+1+16>3n−3n+2+32n−1.Subcase iv:Letdv≥4, and there is no edge between v1 and v. Clearly, it holds that 3≤dv1≤n−3. If we take G5≅G−u1+u2v1, then by using Lemma 10, the inductive hypothesis, and Lemma 11, we get(74)χG=χG5+1du1+du2+1du1+dv1+1du1+dv−1du2+dv1+1du2+dv−1du2+dv−1+∑z∈Nv∖u1,u21dv+dz−1dv−1+dz≥χG5+16+23+dv−13+dv−1+dv−2dv+dz−dv−2dv−1+dz≥χG5+n−2n+1−n−3n+16≥3n−4n+1+32n−2+n−2n+1−n−3n+16.>3n−3n+2+32n−1.Case 3:G does not contain any pair of adjacent vertices of degree 3Letu∈VG be a vertex of degree 3 having neighbors u1, u2, and u3, such that u1u2,u1u3,u2u3∈EG; then clearly, du1,du2,du3≥4. If we take G6≅G−u, then by induction hypothesis and by using Lemma 12, we have(75)χG=χG6+1du+du1+1du+du2+1du+du3+1du1+du2−1du1+du2−2+1du1+du3−1du1+du3−2+1du2+du3−1du2+du3−2+∑z∈Nu1∖u,u2,u31du1+dz−1du1−1+dz+∑z∈Nu2∖u,u1,u31du2+dz−1du2−1+dz+∑z∈Nu3∖u,u1,u21du3+dz−1du3−1+dz≥χG6+13+du1+13+du2+13+du3+1du1+du2−1du1+du2−2+1du1+du3−1du1+du3−2+1du2+du3−1du2+du3−2+du1−3du1+3−du1−3du1+3−1+du2−3du2+3−du2−3du2+3−1+du3−3du3+3−du3−3du3+3−1≥χG6+3n−3n+2−3n−4n+1+32n−1−32n−2≥3n−4n+1+32n−2+3n−3n+2−3n−4n+1+32n−1−32n−2=3n−3n+2+32n−1.
We observe that the equation(76)χG=3n−3n+2+32n−1,holds if and only if(77)du1=du2=du3=n−1.
This completes the proof of Theorem1.


## 5. Concluding Remarks

We have characterized the minimum sum-connectivity index from the family of alln-vertex graphs having minimum degree at least 3, under certain constraints. More precisely, we have been able to show that K3+K¯n−3 is the only graph having minimal sum-connectivity index in the family of all those n-vertex (where n≥23) graphs which have a minimum degree of at least 3 and satisfy the following two conditions:(i)
IfG has a pair of adjacent vertices of degree 3, then this pair of adjacent vertices has at most one common neighbor(ii)
IfG contains no pair of adjacent vertices of degree 3, then G has a vertex of degree 3 whose all neighbors form a triangle.



---

*Source: 1203303-2022-02-04.xml*