# On the Minimum General Sum-Connectivity of Trees of Fixed Order and Pendent Vertices

Authors: Abeer M. Albalahi; Akbar Ali
Journal: Journal of Mathematics
 (2022)

---

## Abstract

For a graphG, its general sum-connectivity is usually denoted by χαG and is defined as the sum of the numbers dGu+dGvα over all edges uv of G, where dGu,dGv represent degrees of the vertices u,v, respectively, and α is a real number. This paper addresses the problem of finding graphs possessing the minimum χα value over the class of all trees with a fixed order n and fixed number of pendent vertices n1 for α>1. This problem is solved here for the case when 4≤n1≤n+5/3 and α>1, by deriving a lower bound on χα for trees in terms of their orders and number of pendent vertices.


---

## Body

## 1. Introduction

We only discuss simple connected graphs in this study. For a graphG, its edge set and vertex set are represented by EG and VG, respectively. Let dGu indicate the degree of a vertex u∈VG. When there is no uncertainty regarding the graph under consideration, we write du instead of dGu. Those (chemical-) graph-theoretical concepts and notation utilized in this article but not described here may be found in related books, such as [1–4].For a graphG, its general sum-connectivity index χαG, devised in [5], is defined as,(1)χαG=∑uv∈EGdu+dvα.where α is a real number. The special cases χ1G and χ−1/2G of χαG yield the first Zagreb index (for example, see [6]) and sum-connectivity index of G [7].A pendent vertex in a graph is a vertex of degree 1. In this paper, we are concerned with the following problem concerning the general sum-connectivity index.Problem 1.
Find the graphs having the maximum and minim general sum-connectivity indexχαamong all trees of a fixed order and number of pendent vertices.
Cui and Zhong [8] studied the maximal part of problem 1 for −1≤α<0. The minimal part of problem 1 for −1≤α<0 was solved in [9]. Tache and Tomescu [10] reported the solution to the maximal part of problem 1 when α≥1; the minimal part was solved in [11] for α=1. Additional information about the known mathematical aspects of the general sum-connectivity index can be found, for example, in [12–16], in [17] (where several general results give special cases for the general sum-connectivity index), and in the related references given therein.
In this paper, a lower bound onχα for trees of order n and number of pendent vertices n1 is derived for n≥1 and α>1. As a consequence of the obtained bound, the minimal part of problem 1 is solved when 4≤n1≤n+5/3 and α>1.


## 2. Main Results

Before proving the main results, we give some definitions and notation that are used in the rest of this section. The star and path graphs withn vertices are represented by Sn and Pn, respectively. A branching vertex of a graph is a vertex of degree greater than 2. For a graph G and a vertex u∈VG, denote by NGu the set of all those vertices of G that are adjacent to u. The elements of the set NGu are known as the neighbors of u. A pendent path u1u2…uk of a graph G is a non-trivial path in G such that one of the vertices u1,uk is pendent and the other is branching, and each ui (if 2≤i≤k−1) has degree 2.Transformation 1. LetT be a tree containing at least two branching vertices. Let u1u2…ur be a pendent path of T such that r≥3, where dTu1≥3 and dTur=1. Choose a vertex w∈ET lying on the unique path between u1 and another branching vertex of T. Suppose that T′ is formed from T by inserting the two edges u1u3, urw, and dropping the two edges u2u3, u1w. The trees T and T′ are depicted in Figure 1.Figure 1
The treesT and T′ specified in Transformation 1, where the subtree Hi may or may not be trivial, i=1,2,…,5.Lemma 1.
IfTandT′are the trees specified in Transformation 1, thenχαT>χαT′forα>1.Proof.
SincedTu1≥3 and dTw≥2, by using the definition of χα, one has(2)χαT−χαT′=dTu1+dTwα−dTu1+1α−dTw+2α+3α≥dTw+3α−4α−dTw+2α+3α≥5α−4α−4α+3α>0,for α>1.
An internal pathu1u2⋯uk of a graph G is a non-trivial path in G such that both the vertices u1,uk are branching, and each ui (if 2≤i≤k−1) has degree 2. Denote by Tn,n1 the class consisting of all trees T with order n, pendent vertices n1, and maximum degree 3 such that every pendent (internal) path of T has length one (at least two, respectively). If T∈Tn,n1 then after simple calculations, one gets.(3)χαT=n−2n1+54α+2n1−35α.Theorem 1.
LetTbe a tree withnvertices, among whichn1are pendent vertices. Then(4)χαT≥n−2n1+54α+2n1−35α=ψαn,n1,where the equality sign in the inequality holds if and only if T∈Tn,n1.Proof.
Forn=1,2,3,4,5, the result is straightforwardly verified. Next, suppose that n≥6. Note that the function fα defined by fαx=x−1xα−2x−45α+x−74α, is strictly increasing for x≥6 and α>1 because fα′x>xα−2⋅5α+4α≥6α−2⋅5α+4α>0. Thus, for n1=n−1 we have T=Sn and hence(5)χαSn−ψαn,n1=n−1nα−2n−45α+n−74α=fαn≥fα6=5⋅6α−4⋅5α−4α>0,for n≥6 and α>1. In what follows, we assume that 2≤n1≤n−2 with n≥6 and we prove the result by using mathematical induction on n1. If n1=2, then T=Pn and(6)χαPn−ψαn,2=2⋅5α−4⋅4α+2⋅3α>0,for α>1. Next, assume that n1≥3 and that the theorem holds for n1−1, where n1≤n−2 and n≥6.Case 1.
The treeT does not contain any pendent path of length greater than 1.
In this case, we consider its several subcases.Subcase 1.
The treeT contains at least one pendent vertex whose neighbor has degree greater than 3.
Letu∈VT be a vertex of degree s having r pendent neighbors u0,u1,…,ur−1 and s−r non-pendent neighbors ur,ur+1,…,us−1, where s≥4 and r≥1. Since n≥6, one has s−r>0. By keeping in mind the inequalities s−r>0, α>1, s≥4, and inductive hypothesis, we have.(7)χαT=χαT−u0+s+1α+r−1s+1α−sα+∑j=rs−1s+dTujα−s+dTuj−1α≥χαT−u0+s+1α+r−1s+1α−sα+s−rs+2α−s+1α=χαT−u0+2r−ss+1α−r−1sα+s−rs+2α≥ψαn,n1+4α−2⋅5α+2r−ss+1α−r−1sα+s−rs+2α=ψαn,n1+s−rs+2α−s+1α+r−1s+1α−sα+s+1α+4α−2⋅5α≥ψαn,n1+6α−5α+5α+4α−2⋅5α>ψαn,n1.Subcase 2.
Every pendent vertex ofT is adjacent to a vertex of degree 3 and there is at least one vertex of degree 3 having only one pendent neighbor.
Letu be a vertex of degree 3 and u0 be a pendent neighbor of u. Assume that u1 and u2 are the non-pendent neighbors of u. By utilizing the induction hypothesis, we get,(8)χαT=χαT−u0+∑i=12dTui+3α−dTui+2α≥χαT−u0+25α−4α+4α≥ψαn,n1,where χαT=ψαn,n1 if and only if dTu1,dTu2∈2 and T−u0∈Tn−1,n1−1; e.g., if and only if T∈Tn,n1.Subcase 3.
Every pendent vertex ofT is adjacent to a vertex of degree 3 and there is at least one vertex of degree 3 having one branching neighbor and two pendent neighbors.
Letu be a vertex of degree 3 and u0,u1 be its two pendent neighbors. Assume that u2 is the non-pendent neighbor of u. By utilizing the induction hypothesis, we get(9)χαT=χαT−u0,u1+dTu2+3α−dTu2+1α+2⋅4α≥χαT−u0,u1+6α+4α≥ψαn−2,n1−1+6α+4α≥ψαn,n1−2⋅5α+6α+4α>ψαn,n1.Subcase 4.
Every pendent vertex ofT is adjacent to a vertex of degree 3, which has one neighbor of degree 2 and two pendent neighbors.
IfT has the maximum degree 3 and if T contains no pair of adjacent vertices of degree 3, then T∈Tn,n1 and we get χαT=ψαn,n1.
Now, assume thatT has the maximum degree 3 and uv∈ET such that dTu=dTv=3. Let w1∈VT be a vertex of degree 3 having two pendent vertices and a vertex w of degree 2. Take NTw=w1,w2. Let T′ be the tree formed from T by deleting the edges uv, w1w, w1w, and adding the edges w1w2, uw, vw. Then, T′ is a tree with n vertices and n1 pendent vertices. Also, note that both the trees T and T′ have the same degree sequence. Since the maximum degree of T is 3, it holds that dTw2=2 or 3. On the other hand, we have(10)χαT−χαT′=dTw2+2α−dTw2+3α+6α−5α≥0.
Note that ifdTw2=3 then χαT=χαT′ and the tree T′ contains a vertex (namely w1) of degree 3 having two pendent neighbors and a neighbor of degree 3, and hence from Subcase 3 it follows that χαT=χαT′>ψαn,n1.
IfdTw2=2 then χαT−χαT′>0. If T′∈Tn,n1 then we are done. If T′ contains at least one pair of adjacent branching vertices then we repeat the above process until we obtain the desired result.
It remains to prove the desired result in the considered case (that is, Subcase4) when the maximum degree of T is greater than 3. Let u′∈VT be a vertex of maximum degree Δ, where Δ≥4. Take NTu′=u1,u2,…,uΔ and let v′∈VT be a vertex of degree 3 having two pendent neighbors and a neighbor of degree 2. Let v1 be a pendent neighbor of v′. Without loss of generality, we assume that u2 lies on the unique u′-v′ path. Let T″ be the tree deduced from T by deleting the edge u1u′ and inserting the edge u1v′. Observe that the tree T′′ has n vertices among which n1−1 are pendent. Thus, by using the the inequalities dTu=Δ≥4, dTui≥2, i∈1,2,…,Δ (because of the considered case), and inductive hypothesis, we have(11)χαT=χαT″+∑i=2ΔdTui+Δα−dTui+Δ−1α+dTu1+Δα−dTu1+2α+4α−6α≥χαT′′+Δ−1Δ+2α−Δ+1α+Δ+2α−6α≥χαT′′+36α−5α≥ψαn,n1+24α−5α+36α−5α>ψαn,n1,for α>1.Case 2.
T contains at least one pendent path of length greater than 1.
First, we suppose thatT contains only one branching vertex. Assume also that T contains at least two pendent paths of lengths at least 2. Let u0u1u2⋯ur and v0v1v2⋯vs be two such pendent paths, where u0,v0 are branching vertices and ur,vs are pendent vertices. Let T′ be the tree formed by deleting the edge u1u2 and adding the edge u2vs. Since α>1 and n1≥3, we have(12)χαT−χαT′=n1+2α−n1+1α−4α−3α≥5α−4α−4α−3α>0,Thus, from the above discussion, we conclude that if T contains only one branching vertex then(13)χαT≥χαT⋆=n−n1−24α+n1+2α+n1−1n1+1α+3α,where T⋆ is a tree formed by attaching n1−1 pendent vertices to one of the pendent vertices of the path graph Pn−n1+1. For 3≤n1≤8, by direct calculations it is verified that the inequality(14)n−n1−24α+n1+2α+n1−1n1+1α+3α>ψαn,n1,holds for α>1 Also, for n1≥9 and α>1, one has(15)n−n1−24α+n1+2α+n1−1n1+1α+3α−ψαn,n1>n1−1n1+1α−2n1−35α,the right hand side of this inequality is positive because(16)n1−1n1−3n1+15α>n1+15α≥2α>2.
Therefore,(17)χαT≥χαT⋆>ψαn,n1.
Next, we suppose thatT contains at least two branching vertices. By Transformation 1 and Lemma 1 there exists a tree T† of order n with n1 pendent vertices such that T† contains no pendent path of length greater than 1 and χαT>χαT†. However, by Case 1, it holds that χαT†≥ψαn,n1. Therefore, χαT>ψαn,n1. This completes the proof.
Observe that the classTn,n1 is non-empty whenever n1≥4 and n≥3n1−5. Thus, the next result immediately follows from Theorem 1.Corollary 1.
Forα>1and4≤n1≤n+5/3, among all trees with ordernand number of pendent verticesn1, the elementsof the classTn,n1uniquely minimize the general sum-connectivity indexχα.


## 3. Concluding remarks

For a graphG, its general Platt index [18] is defined as(18)PlαG=∑uv∈EGdu+dv−2α,where α is a real number. The graph invariant Pl2G is known as the reformulated first Zagreb index of G [19]. Because of the similarity between the definitions of χα and Plα, one obtains Theorem 2 (corresponding to Theorem 1) and Corollary 1 (corresponding to Corollary 2).Theorem 2.
LetTbe a tree withnvertices, among whichn1are pendent vertices. Then(19)PlαT≥n−2n1+52α+2n1−33α,where the equality sign in the inequality holds if and only if T∈Tn,n1.Corollary 2.
Forα>1and4≤n1≤n+5/3, among all trees with ordernand number of pendent verticesn1, the elementsof the classTn,n1uniquely minimize the general Platt indexPlα.



---

*Source: 8567266-2022-06-06.xml*