# Investigation of General Power Sum-Connectivity Index for Some Classes of Extremal Graphs

Authors: Rui Cheng; Gohar Ali; Gul Rahmat; Muhammad Yasin Khan; Andrea Semanicova-Fenovcikova; Jia-Bao Liu
Journal: Complexity
 (2021)

---

## Abstract

In this work, we introduce a new topological index called a general power sum-connectivity index and we discuss this graph invariant for some classes of extremal graphs. This index is defined byYαG=∑uv∈EGdudu+dvdvα, where du and dv represent the degree of vertices u and v, respectively, and α≥1. A connected graph G is called a k-generalized quasi-tree if there exists a subset Vk⊂VG of cardinality k such that the graph G−Vk is a tree but for any subset Vk−1⊂VG of cardinality k−1, the graph G−Vk−1 is not a tree. In this work, we find a sharp lower and some sharp upper bounds for this new sum-connectivity index.


---

## Body

## 1. Introduction

In this article, all the graphs are considered as simple, connected, finite, and undirected. Let us denote a graph byG=VG,EG, where VG and EG represent the sets of vertices and edges, respectively. Degree of vertex u is the number of adjacent vertices to u and is denoted by du, and the set of vertices adjacent to the vertex u is denoted by Nu. The length of a shortest path between two vertices, say u and v, is termed as the distance between these vertices and is denoted by du,v. The maximum distance from vertex u to any other vertex is known as the eccentricity of the vertex u and is denoted by εu and defined as εu=maxv∈VGdu,v. The diameter of a graph G is maxu∈VG=maxu,v∈VG, and its notation is diamG; further, see [1–3].LetKn be a complete graph of order n. The complete bipartite graph K1,n−1, which is also denoted as Sn, represents a star of order n, while Pn is the path of order n and size n−1. A double star of order a+b is denoted by Sa,b. The graph Sa,b is a tree which consists of two adjacent vertices say u and v, such that u is adjacent to b−1 pendent vertices and v is adjacent to a−1 pendent vertices. Alternatively, the double star Sa,b can be obtained by joining the centers of two stars Sa+1 and Sb+1. If for a tree T the diameter of T is 2, then T is a star graph, and if the diameter of T is 3, then T is a double star. For two graphs G and H whose vertex sets are disjoint, G+H denotes its join graph having the vertex set VG+H=VG∪VH and EG+H=EG∪EH∪uv:u∈VG,v∈VH is its edge set.If there exists a vertexv in a graph G such that the graph G−V is a tree, then the graph G is called a quasi-tree and the vertex v is called a quasi-vertex. Obviously, every tree is a quasi-tree, as by deletion of any vertex in a tree, the resulting graph is again a tree. Furthermore, a k-generalized quasi-tree is a graph in which there exists a subset Vk⊂VG with cardinality k such that the graph G−Vk is a tree but for any subset Vk−1⊂VG with cardinality k−1, the graph G−Vk−1 is not a tree. The vertices in the set Vk are called k-quasi-vertices or quasi-vertices. We need at least k+2 vertices for sketching k-generalized quasi-tree. Any tree is a quasi-tree which is trivial. Let the class of k-generalized quasi-trees of order n be denoted by Tkn.In this modern world, the network structure plays the basic role in the field of chemistry, technology, and communication. Every network is distinguished by means of numerical quantity under some parameter. Such roles are called topological indices. A numerical quantity that is invariant under graph automorphisms is termed as the topological index. There are many topological indices such as degree-based, distance-based, and counting-related topological indices. In all the said indices, degree-based topological indices are one of the basic indices and play the key role in chemistry and chemical graph theory. The mostly studied topological indices are the atom-bond (ABC) connectivity index, the harmonic (H) index, the Zagreb index, and various others; further we refer to [4–10].On the basis of the previously defined indices, we introduce a new sum-connectivity index called a general power sum-connectivity index defined such that(1)YαG=∑uv∈EGdudu+dvdvα,α≥1.


## 2. Main Work

This section is devoted to the main results which we proved for the new introduced sum-connectivity index for some classes of extremal graphs. The following are the main results in this regard.Lemma 1.
For any two verticesuandv∈VG, where uv∉EG, then(2)YαG<YαG+uv.Theorem 1.
The general power sum-connectivity indexYαG is minimum for a graph G if G=Pn, for n≥4 and α≥1.Proof.
LetG be the graph of order n. To prove that YαG is minimum for G=Pn, where n≥4, we consider two cases.Case 1.
Whenn=4, in this case, the graph is isomorphic either to a path P4 or to a star S4, see Figure 1.
In this case, we have(3)YαP4=2⋅5α+8α,and similarly,(4)YαS4=3⋅28α.
It is obvious thatYαP4<YαS4. Equality holds if α=0. This can be easily analyzed through the following plot illustrated on Figure 2.Figure 1
A pathP4 and a star S4.Figure 2
Plot forYαP4 and YαS4.Case 2.
Whenn≥5, in this case, suppose on contrary that YaPn is not minimum. Then, there exists a graph other than Pn in which at least one vertex, say y, has degree greater than 2, i.e., such that dGy≥3. We have to discuss the following subcases .
Subcase B1: wheny is adjacent to two leaves. A graph for this case is shown in Figure 3.Here, we have(5)YαG=5α+n−5⋅8α+31α+2⋅28α,and forPn, we have(6)YαPn=2⋅5α+n−3⋅8α.From (5) and (6), this is obvious that YαG>YαPn which can be determined through the following plots illustrated on Figure 4 for various values of n.This is a contradiction to the minimality ofYαG. Hence, in this case, YαPn is minimal.Subcase B2: wheny is adjacent to only one leaf. In this case, the graph is illustrated in Figure 5.Here,YαG is given below:(7)YαG=1+22α+22+33α+22+33α+1+33α+22+22α+22+22α+⋯+1+22α=2⋅5α+2⋅31α+n−6⋅8α+28α.Obviously, from (6) and (7), we have YαG>YαPn which can be observed through the following plots, see Figure 6, for various values of n, which is a contradiction to the minimality of YαG.Figure 3
A graphG with a vertex y adjacent to two leaves.Figure 4
Plot forYαG and YαPn for various values of n.Figure 5
A graphG with a vertex y adjacent to one leaf.Figure 6
Plot forYαG and YαPn for various values of n.Lemma 2.
LetG∈Tkn, where Tkn is the class of k-generalized quasi-trees. If YαG is maximum and w is a quasi-vertex of G, then dGw=n−1.Proof.
Consider thatG is a k-generalized quasi-tree from Tkn, where YαG is maximum for G and let w be a quasi-vertex of G. We show that dGw=n−1. On contrary, suppose that YαG is maximum for G and dGw<n−1. Then, there is a vertex f which is not adjacent to w. Then, by means of Lemma 1, we have(8)YαG<YαG+wf,which is a contradiction to the maximality of YαG. Hence, we are forced to accept that dGw=n−1.
Roughly speaking that, forα≥1, we define the following function:(9)Fz1,z2,z3,…,zj=z1α⋅z1+z2α⋅z2+z3α⋅z3+⋯+zjα⋅zj,which is defined for z1,z2,z3,…,zj∈Hj,q, where Hj,q is a set containing vectors z1,z2,z3,…,zj having coordinates from positive integers and satisfying the following:(10)z1≥z2≥z3≥⋯≥zj≥1,q=∑i=1jzi.
Further, for1≤i<k≤j and zk≥2, we replace the components of z1,z2,…,zj by z1,z2,…,zi+1,…,zk−1,…,zj, rearranging the replaced components in decreasing order as(11)z1∗,z2∗,z3∗,…,zj∗.
Letz1∗,z2∗,z3∗,…,zj∗=z∗; then, obviously z∗∈Hj,q. Let this transformation be denoted by A1. Next, we have(12)Fz∗−Fz1=zi+1α⋅zi+1+zk−1α⋅zk−1−ziα⋅zi−zkα⋅zk.
We define another function:(13)ψz=zα⋅z−1+zα⋅1+z.
This function is a strictly decreasing function forz>0 and α≥1. Thus, if i<k, then zi≥zk which implies that zk−1<zi, and thus, ψzk−1>ψzi. This is due the decreasing function. We can also obtain that(14)zk−1α⋅zk−1−zkα⋅zk>ziα⋅zi−1+ziα⋅1+zi,zk−1α⋅zk−1+1+ziα⋅1+zi>ziα⋅zi+zkα⋅zk.
We obtained thatFz∗−Fz1,z2,…,zj>0. We can easily deduce the following result.Lemma 3.
If there is an2≤k≤j having xk≥2, then Fz1,z2,…,zj is strictly decreasing on Hj,q having α≥1.
In other words, we observe that the function is strictly increased if we push one unity to the left in the degree sequence and arrange this new sequence in decreasing order using theA1 transformation.Theorem 2.
LetT be a tree in Tn, where Tn is the class of trees of order n. Then, YαT is maximum if T is the star graph Sn.Proof.
LetT∈Tn, such that YαT is maximum. We need to prove that T=Sn. For this proof, suppose on contrary that YαT is maximum and T is neither a star Sn nor a double star. Then, there is a vertex in T, say t, which is adjacent to two vertices x and y, such that dTx=a, dTy=b, and dTt=c, where aandb≥2. Without loss of generality, let a≥b, see Figure 7.
Furthermore, for the neighbors ofx and y, we have Nx−t=x1,x2,…,xa−1 and Ny−t=y1,y2,…,yb−1. We can construct another tree T∗ from T in such a way that we delete the edges yy1,yy2,…,yyb−1 and we insert new edges xy1,xy2,…,xyb−1 as in [11]. Now, we have the following:(15)YαT∗=∑i=1a−1a+b−1a+b−1+dT∗xidT∗xiα+∑i=1b−1a+b−1a+b−1+dT∗yidT∗yiα+a+b−1a+b−1+ccα+cc+1α.
Similarly, forT, we have(16)YαT=∑i=1a−1a+dTxidTxiα+∑i=1b−1b+dTyidTyiα+aa+ccα+cc+bbα.
Next, we get the following:(17)YαT∗−YαT>a+b−1a+b−1+ccα+cc+1α−aa+ccα−cc+bbα>0.
As a consequence of Lemma3, for j=2 and z1=aa+cc, z2=cc+bb, q=aa+bb+2⋅cc, and applying the transformation A1 several times, we get a contradiction to the maximality of YαT. Now, we show that, for aandb≥2 and a+b=n, we have the following:(18)YαSn>YαSa,b.
ForSn and Sa,b, we obtain(19)YαSn=n−1n−1n−1+1α,YαSa,b=a−1a−1a−1+1α+b−1b−1b−1+1α+aa+bbα.
Their difference holds(20)YαSn−YαSa,b=n−1n−1n−1+1α−a−1a−1a−1+1α−b−1b−1b−1+1α−aa+bbα>0.
The reason of the above last inequality can be easily determined asn−1>a and n−1>b which implies that n−1n−1>a−1a−1 and n−1n−1>b−1b−1. This further implies that n−1n−1+1>a−1a−1+1 and n−1n−1+1>b−1b−1+1 where α≥1. Hence, YαSn>YαSa,b. This completes the proof.
In a graphG, if the weight of every vertex is fixed, let such weight be r≥1; then, we define(21)Yα,rG=∑uv∈EGdudu+dvdv+2rα.Figure 7
A treeT.Theorem 3.
For anyα≥1 and r≥1, the unique tree of order n having maximum value of Yα,rG is Sn.Proof.
On contrary base, letT be a tree having maximum value of Yα,rG, where T is neither a star nor a double star say Sa,b. Then, diamT is greater or equal to 4. Then, there is a vertex in T, say t, that is adjacent to two vertices say x and y, such that dTx=a, dTy=b, and dTt=c without loss of generality let aandb≥2. Such a tree is shown in Figure 7 while considering that every vertex has the fixed weight. Furthermore, for x and y, we can have that Nx−t=x1,x2,…,xa−1 and Ny−t=y1,y2,…,yb−1. We can easily construct another tree T∗ from T by eliminating the edges yy1,yy2,…,yyb−1 and adding new edges xy1,xy2,…,xyb−1; for this, we refer [11]. For our proof, we proceed as follows:(22)Yα,rT∗=∑i=1a−1a+b−1a+b−1+dT∗xidT∗xi+2rα+∑i=1b−1a+b−1a+b−1+dT∗yidT∗yi+2rα+a+b−1a+b−1+cc+2rα+cc+1+2rα.
On similar way forT, we have(23)Yα,rT=∑i=1a−1aa+dTxidTxi+2rα+∑i=1b−1bb+dTyidTyi+2rα+aa+cc+2rα+cc+bb+2rα.
As in Theorem2, we can easily show that there is a contradiction to the maximality of Yα,rG, where G=T. Also, the following holds:(24)Yα,rSn−Yα,rSa,b=n−1n−1n−1+1+2rα−a−1a−1a−1+1+2rα−b−1b−1b−1+1+2rα−aa+bb+2rα>0.
The last inequality can easily be determined asn−1>a and n−1>b which implies that n−1n−1>a−1a−1, n−1n−1>b−1b−1. This further implies that n−1n−1+1+2r>a−1a−1+1+2r and n−1n−1+1+2r>b−1b−1+1+2r, where α≥1. Hence, Yα,rSn>Yα,rSa,b.Theorem 4.
Fork≥1, let G∈Tkn. If YαG is minimum and w be a quasi-vertex of G, then dw=2.Proof.
LetG∈Tkn such that YαG is minimum. We have to show that dw=2 where w is quasi-vertex. On contrary base, suppose that dw=1. In this case, w cannot be quasi-vertex because w will be pendent vertex and w will make no difference in the formation of quasi-tree. On the contrary, let dw≥2, and this shows that w is adjacent to more than two vertices in G. Therefore, for elimination of any edge wd∈EG, we have YαG>YαG−wd where YαG−wd∈Tkn. This is contradiction to the minimality of YαG. This contradiction is due to our wrong supposition that dw≥2. Hence, in both cases, there is contradiction due to which we are forced to accept that dw=2.Theorem 5.
LetG∈Tkn, where k≥1 and n≥5. α≥1 holds(25)YαG≤2α−1kk+1n−1α⋅n−1+k+1n−k−1n−1n−1+k+1k+1α,where the equality is satisfied if and only if G=Kk+Sn−k.Proof.
LetG∈Tkn and α≥1 be such that YαG is maximum as possible. Let the set of quasi-vertex be represented by Vk⊂VG. By means of Lemmas 1 and 2, we have G=Kk+Tn−k, where Tn−k is a tree of order n−k. We have to prove that Tn−k=Sn−k. For this, we have, from [4],(26)YαG=YαKk+Tn−k=∑uv∈EKkdGudGu+dGvdGvα+∑u∈VKkv∈VTn−kdGudGu+dGvdGvα+∑uv∈ETn−kdGudGu+dGvdGvα.
We calculate each sum separately:(27)∑uv∈EKkdGudGu+dGvdGvα=2α−1kk−1⋅n−1α⋅n−1.
Similarly, the middle sum in (26) can be obtained as(28)∑u∈VKkv∈VTn−kdGudGu+dGvdGvα=k∑v∈VTn−kn−1n−1+dTn−kv+kdTn−kv+kα.
Using Theorem2, the sum in (28) attains its maximum if Tn−k=Sn−k. For this, the above last sum becomes(29)∑u∈VKkv∈VSn−kdGudGu+dGvdGvα=kn−k−1n−1n−1+k+1k+1α+2αkn−1αn−1.
Similarly, the last sum in (26) is calculated as follows:(30)∑uv∈ETn−kdGudGu+dGvdGvα=∑uv∈ETn−kdTn−ku+kdTn−ku+k+dTn−kv+kdTn−kv+kα.
By means of Theorem2, the above last sum will obtain its maximum if Tn−k=Sn−k. For this, we have the following:(31)∑uv∈ESn−kdSn−ku+kdSn−ku+k+dSn−kv+kdSn−kv+kα=n−k−11+k1+k+n−1n−1α.
Combining (27), (29), and (31), we have Tn−k=Sn−k, and consequently, for G=Kk+Sn−k, we get the following:(32)YαG=2α−1kk+1n−1α⋅n−1+k+1n−k−1n−1n−1+k+1k+1α.Theorem 6.
LetG∈Tkn and α≥1.(i)
Ifk=1 and n≥3, then YαG≥n⋅8α. The equality YαG=n⋅8α holds if and only if G=Cn, where Cn is a cycle of order n.(ii)
Ifk=2 and n=4, then YαG≥54α+4⋅31α. If k=2 and n≥5, then YαG≥6⋅31α+n−5⋅8α. Furthermore, the equality holds if and only if G consists of two cycles of length three having a common edge for n=4 or two cycles with a common path having length at least two for n≥5 or two cycles joined by a path of length at least two for n≥7.Proof.
Suppose thatG∈Tkn, where YαG is as small as possible. Let the set of quasi-vertices be Vk; then, by the definition of a k-generalized quasi-tree, G−Vk is a tree having order n−k. By Theorem 5, we have ds=2 for all s∈Vk. Furthermore, for every vertex s in Vk, s is adjacent to two vertices of V−Vk. From this discussion, we deduce that G is a connected graph with n+k−1 edges. It means that G has internal k-cycles. First of all, we have to show that G has no pendent vertex. For this, suppose on contrary base that G has a pendent vertex x. Let there be another vertex z where there is a path between x and z, and let also z belong to a cycle, say C, in G. Let this path be x,v,…,z. We denote the vertices adjacent to v different from x by x1,x2,…,xt, and let their degrees be dxi=di, 1≤i≤t. Then, we have dGv=t+1. Obviously, t≥1 and at least one degree di≥2. We can define a new k-cyclic graph having order n, by deleting the edge between x and v and then arranging x between two consecutive vertices, say g and h, on the cycle C. Let dGg=a and dGh=b; clearly, aandb≥2. Then, in the new graph, say G∗, the degree of v is t, dG∗g=a, dG∗h=b, and dG∗xi=di for every 1≤i≤t. We can write the difference of YαG−YαG∗ as(33)YαG−YαG∗=∑uv∈EGdGudGu+dGvdGvα−∑ef∈EG∗dG∗edG∗e+dG∗fdG∗fα=∑i=1tt+1t+1+didiα−tt+didiα+t+1t+1+1α+aa+bbα−aa+22α−bb+22α.
Fort≥2, we have the following:(34)∑i=1tt+1t+1+didiα−tt+didiα>0.
Also,t+1t+1+1α≥28α; by using Lemma 3, we have t+1t+1+1α+aa+bbα−aa+22α−bb+22α>0, which shows that YαG−YαG∗>0. This is a contradiction to the minimality of G, that is, G∗ is another k-cyclic graph having YαG∗ smaller than that of YαG.
Now, fort=1, it implies that v is a pendent vertex of G∗; by doing the same process for v instead of x, we will observe that there is a pendent vertex v that is adjacent to z on cycle C; then, dz≥3 in this case. We will again get a contradiction, and this contradiction is due to our wrong supposition; hence, we are forced to accept that ds≠1.
Next, we have to suppose that, for alls∈VG, ds≥2 .(i)
Then, fork=1, this implies that G is a connected graph having one cycle and n edges. Obviously, G=Cn; thus, each vertex of G has degree 2, and then,(35)YαG=n⋅8α.Otherwise,YαG will be greater than that of n.8α.(ii)
Fork=2, it shows that G is a 2-cyclic graph and has n+1 edges. Now, the sum of degrees of G is given in the following:(36)∑v∈Gdv=2+2n.Let us denote these degree sequences byd∗ or d∗∗, that is,(37)d∗G=3,3,2,2,…,2,or(38)d∗∗G=4,2,2,…,2.If the degree sequence ofG is d∗, then(a)
The graphG contains a common path of length L≥1, or(b)
The graphG has two cycles joined by a path of length L≥1In these cases, ifL=1, then such graph is shown in Figure 8.For this, we have(39)YαG=54α+4⋅31α+n−4⋅8α=A.IfL=2, then we have a graph illustrated in Figure 9.For this graph, we obtain(40)YαG=6⋅31α+n−5⋅8α=B.If degree sequence ofG is d∗∗, then in this case G has two cycles having a vertex in common, as shown in Figure 10.For this graph, we get(41)YαG=4⋅260α+n−3⋅8α=C.FromA, B, and C, we have A>B which is equivalent to 8α+54α>2⋅31α and is obvious which can be easily determined through Figure 11. Now, C>A which implies that C−A is positive. This can be seen in Figure 12.Figure 8
A graph for the degree sequenced∗ and L=1.Figure 9
A graph for the degree sequenced∗ and L=2.Figure 10
Graph for degree sequenced∗∗.Figure 11
Plot forA−B, and it shows that A>B.Figure 12
Plot forC−A, and it shows that C>A.



---

*Source: 6623277-2021-08-23.xml*