# On Variable Sum Exdeg Indices of Quasi-Tree Graphs and Unicyclic Graphs

Authors: Xiaoling Sun; Jianwei Du
Journal: Discrete Dynamics in Nature and Society
 (2020)

---

## Abstract

In this work, by using the properties of the variable sum exdeg indices and analyzing the structure of the quasi-tree graphs and unicyclic graphs, the minimum and maximum variable sum exdeg indices of quasi-tree graphs and quasi-tree graphs with perfect matchings were presented; the minimum and maximum variable sum exdeg indices of unicyclic graphs with given pendant vertices and cycle length were determined.


---

## Body

## 1. Introduction

Topological indices are mathematical descriptors reflecting some structural characteristics of organic molecules on molecular graphs, and they play an important role in pharmacology, chemistry, etc. ([1–3]). For a graph G, the variable sum exdeg index (denoted by SEIa) was proposed by Vukičević [4] and is defined as(1)SEIaG=∑uv∈EGadGu+adGv=∑v∈VGdGvadGv,where a∈0,1∪1,+∞ and dGv is the degree of vertex v. This graph invariant has a good correlation with the octanol-water partition coefficient [4] and was used to study the octane isomers given by the International Academy of Mathematical Chemistry (IAMC) [5–7]. Yarahmadi and Ashrafi [8] proposed a polynomial form of this graph invariant which is applied in nanoscience. By using the technique of majorization, Ghalavand and Ashrafi [9] provided the maximal and minimal SEIa (for a>1) of trees, bicyclic graphs, unicyclic graphs, and tricyclic graphs.All graphs considered in this work are simple connected graphs. LetG=VG,EG be a graph with the vertex set VG and the edge set EG. We denote by δG the minimum degree of G. We use NGv to denote the neighbourhood of a vertex v and ni to denote the number of vertices with degree i. Denoted by G−uv and G+uv the graphs arisen from G by deleting the edge uv∈EG and by adding the edge uv∉EGu,v∈VG, respectively. We denote by G−x the subgraph of G resulted by deleting the vertex xx∈VG with its incident edges. We call G a quasi-tree graph if there is a vertex x in G such that G−x is a tree. A unicyclic graph is the graph with exactly one cycle. Let G1 and G2 be two vertex-disjoint graphs. We denote by G1∨G2 the graph having vertex set VG1∨G2=VG1∪VG2 and edge set EG1∨G2=EG1∪EG2∪xyx∈VG1,y∈VG2. As usual, we use Pn, Sn, and Cn to denote the n-vertex path, the n-vertex star, and the n-vertex cycle, respectively. The readers should refer for other definitions to [10].There are many papers on the mathematical properties of topological indices, such as [11–14], since these invariants can detect the desirable properties of chemical molecules. In this work, we studied the mathematical properties of SEIa. This article is structured as follows. In Section 2, we present some useful lemmas. In Section 3, we obtain the maximal and minimal SEIa (for a>1) of quasi-tree graphs. In Section 4, we determine the maximal and minimal SEIa (for a>1) of quasi-tree graphs with perfect matchings. In Section 5, we derive the maximal and minimal SEIa (for a>1) of unicyclic graphs with given cycle length. In Section 6, we find the maximal and minimal SEIa (for a>1) of unicyclic graphs with given pendant vertex.


## 2. Preliminaries

Lemma 1 (see [6]).
Letfax=xax, where x≥1,a>1. Then(i)
fax is strictly monotone increasing in x(ii)
fa″x>0 and fax is strictly convexBy Lemma1, we have Lemmas 2 and 3 immediately.Lemma 2.
SupposeG=VG,EG is a connected graph, then(i)
Ife∈EG, SEIaG>SEIaG−e for a>1(ii)
Ife=uv∉EG,u,v∈VG, SEIaG<SEIaG+e for a>1Lemma 3.
Letx1,y1,x2andy2 be positive integers with x1+x2=y1+y2 and y1−y2>x1−x2. Then for a>1, we have(2)x1ax1+x2ax2<y1ay1+y2ay2.By simple calculation, Lemma4 is immediate.Lemma 4.
Let(3)lx=fax−fax−1=xax−x−1ax−1,where a>1, x≥2. Then lx is strictly monotone increasing in x.Lemma 5.
Let(4)gk=k+1ak+1+2k−2a2−3k−1a3,where k≥3 and a>1. Then gk>0.Proof.
Note that(5)g′k=k+1ak+1lna+ak+1−3a3+2a2.(6)g′′k=lna2ak+1+k+1ak+1lna>0.
So,g′k≥g′3=a4−3a3+2a2+4a4lna. Let ha=a4−3a3+2a2+4a4lna, where a≥1. Then(7)h′a=a8a2−9a+4+16a3lna>0.
Thus,g′k≥g′3=ha>h1=0. So, gk≥g3=4a4−6a3+2a2=2a2a−12a−1>0 for a>1.


## 3. Variable Sum Exdeg Indices of Quasi-Tree Graphs

SupposeG is a quasi-tree graph and x is a vertex in G such that G−x is a tree. If dGx=1, then G is a tree with extremal variable sum exdeg index (for a>1), that had been presented in [6, 9]. Thus, we always consider the case of dGx≥2 in this section. Let.QTn=HHis a quasi−tree graph onnvertices withdGx≥2.LetQn be the graph arisen from complete bipartite graph K2,n−2 by adding one edge between the two nonadjacent vertices with degree n−2, as shown in Figure 1. We can easily obtain that SEIaQn=2n−1an−1+2n−2a2.Figure 1
The graphQn.Lemma 6.
SupposeG∈QTn such that G has the maximal value of SEIa for a>1. Let x∈VG such that G−x is a tree. Then, δG≥2 and dGx=n−1.Proof.
IfdGx<n−1, then there exists z∈VG such that xz∉VG. Clearly, G+xz∈QTn. In view of Lemma 2, SEIaG+xz>SEIaG, a contradiction. Therefore dGx=n−1, and it can be concluded that δG≥2.Theorem 1.
LetG∈QTn, where n≥3. Then, for a>1,(8)2na2≤SEIaG≤2n−2a2+2n−1an−1,with the left equality if and only if G≅Cn and with the right equality if and only if G≅Qn.Proof.
By induction onn. When n=3, it follows that G≅C3 and (8) holds. Assume that n≥4 and (8) holds for QTn−1.
First, we obtain the lower bound. If there is no pendant vertex inG, since G∈QTn, then there exists u∈VG such that dGu=2. Let NGu=v1,v2. For v1v2∉EG, let G′=G−u+v1v2∈QTn−1. By (1) and induction hypothesis, for a>1, we have(9)SEIaG=SEIaG′+2a2≥2n−1a2+2a2=2na2,with equality holding only if G′≅Cn−1. This implies G≅Cn.
Forv1v2∈EG, let G′′=G−u∈QTn−1. By i of Lemma 1 and induction hypothesis, for a>1, we have(10)SEIaG=SEIaG′′+2a2+dGv1adGv1−dGv1−1adGv1−1+dGv2adGv2−dGv2−1adGv2−1>2n−1a2+2a2=2na2.
Otherwise, there is at least one pendant vertex inG. Let y∈VG and dGy=1. Then, G−y∈QTn−1. We denote by z the vertex with yz∈EG. It can be seen that dGz≥2. If dGz=2, then G−y≇Cn. By (1) and induction hypothesis, for a>1, we have(11)SEIaG=SEIaG−y+2a2>2n−1a2+2a2=2na2.
IfdGz>2, then by (1), (2), Lemma 4, and induction hypothesis, for a>1, it follows that(12)SEIaG=SEIaG−y+a+dGzadGz−dGz−1adGz−1≥2n−1a2+a+3a3−2a2=2na2+3a3+a−2⋅2a2>2na2.
Next, we obtain the upper bound. ChooseG∈QTn such that G has the maximum SEIa for a>1. By Lemma 6, δG≥2. Then, there is a vertex v in G such that dGv=2 since G is a quasi-tree graph. By Lemma 6, it follows that G−v∈QTn−1. Denote NGv=w1,w2. If dGw1=dGw2=n−1, then G−w1,w2 has no edges. This implies that G≅Qn. If one of the vertices w1,w2, say w1, satisfies dGw1<n−1, then G≇Qn. By (1), Lemma 1, and induction hypothesis, we have(13)SEIaG=SEIaG−v+2a2+dGw1adGw1−dGw1−1adGw1−1+dGw2adGw2−dGw2−1adGw2−1≤2n−3a2+2a2+2n−2an−2+dGw1adGw1−dGw1−1adGw1−1+dGw2adGw2−dGw2−1adGw2−1=2n−2a2+2n−1an−1−2n−1an−1−2n−2an−2−dGw1adGw1−dGw1−1adGw1−1+dGw2adGw2−dGw2−1adGw2−1=SEIaQn−2fa′ξ−fa′η1−fa′η2=SEIaQn−fa′ξ−fa′η1+fa′ξ−fa′η2<SEIaQn,where n−2<ξ<n−1, dGw1−1<η1<dGw1, dGw2−1<η2<dGw2, and ξ>η1, ξ≥η2.
In [6], Vukičević obtained the minimal and maximal SEIa of trees on n vertices for a>1. The result is shown below.Theorem 2 (see [6]).
SupposeT is a tree on n vertices, then for a>1,(14)2n−2a2+2a≤SEIaT≤n−1an−1+n−1a,where the left equality holds only when G≅Pn, and the right equality holds only when G≅Sn.Thus, by simple calculation, we can extend our result to the whole quasi-tree graphs, as follows.Theorem 3.
LetG be an n-vertex quasi-tree graph. Then, for a>1,(15)2n−2a2+2a≤SEIaG≤2n−2a2+2n−1an−1,where the left equality holds if and only if G≅Pn and the right equality holds if and only if G≅Qn.


## 4. Variable Sum Exdeg Indices of Quasi-Tree Graphs with a Perfect Matching

LetT1 be the tree of order 2k−1 arisen from Sk+1 by adding a pendant edge to its k−2 pendant vertices, as shown in Figure 2. Let T2 be the tree of order 2k−1 arisen from Sk by adding a pendant edge to its every pendant vertex, as shown in Figure 2. Let QT12k=T1∨K1 and QT22k=T2∨K1.Figure 2
The graphT1 and T2.
(a)(b)Lemma 7.
Letk≥3 be positive integers. Then, for a>1,(16)SEIaQT12k>SEIaQT22k.Proof.
By (1) (2) and Lemma 4, for a>1, we have(17)SEIaQT12k−SEIaQT22k=2k−1a2k−1+k+1ak+1+2ka2+3k−2a3−2k−1a2k−1−kak−2k−1a2−3k−1a3=k+1ak+1−kak+2a2−3a3≥4a4+2a2−2⋅3a3>0,since k≥3.Theorem 4.
LetG be a quasi-tree graph of order 2k with a perfect matching, where k≥2. Then, for a>1,(18)SEIaG≤2k−1a2k−1+k+1ak+1+3k−2a3+2ka2,with equality only when G≅QT12k.Proof.
Whenk=2, G∈G1,G2,G3,QT14 (as shown in Figure 3). By Lemma 2, we have SEIaQT14>SEIaGi, i = 1, 2, 3.
Ifk≥3, choose G such that G has the maximal value of SEIa for a>1. Assume that M is a perfect matching of G. We can suppose that T=G−x is a tree since G are quasi-tree graphs. Choose y∈VT such that dTy=maxdTuu∈VT.Figure 3
The graphG1, G2, G3 and QT1(4).
(a)(b)(c)(d)Claim 1.
For any vertexv of T, xv∈EG.
The proof is similar to Lemma6 (thus omitted).Claim 2.
For any vertexu of T except y, dTu≤2.
To the contrary, assume that there isy′∈VT\y such that dTy′≥3. Let NTy=u1,u2,…,ur and NTy′=v1,v2,…,vs, where r≥s≥3. By Claim 1, dGy=r+1 and dGy′=s+1. Since T is a tree, we suppose that P is the unique path P from y to y′ in T. Assume without loss of generality that u1,v1∈VP (maybe u1=y′ or v1=y ). Notice that M∩v2y′,v3y′,…,vsy′≤1. Without loss of generality, assume that v3y′,…,vsy′∉M. Let G′=G−v3y′,…,vsy′+v3y,…,vsy. Clearly, G′ is also a quasi-tree graph of order 2k with a perfect matching. By (1) and (2),(19)SEIaG′−SEIaG=r+s−1ar+s−1+3a3−s+1as+1−r+1ar+1>0,a contradiction with the choice of the graph G.
By Claim2, T is a tree with some pendant paths attached to y.Claim 3.
dTy≥3.
On the contrary, assume thatdTy≤2. By the choice of y, dTy≥2, thus dTy=2 and T is a path on 2k−1 vertices. Denote T=x1x2…x2k−1. By Claim 1, xxi∈EG, i=1,2,…,2k−1. It is not difficult to get that SEIaG=2k−1a2k−1+32k−3a3+4a2. By Lemma 5, for a>1 and k≥3, we have(20)SEIaQT12k−SEIaG=k+1ak+1+2k−1a2k−1+3k−2a3+2ka2−2k−1a2k−1−32k−3a3−4a2=k+1ak+1−3k−1a3+2k−2a2>0,a contradiction with the choice of the graph G.
We denote byP1,P2,…,Pt (t≥3) the paths attached to y in T.Claim 4.
EPi≤2 for 1≤i≤t in T.
To the contrary, suppose without loss of generality thatEP1≥3 in T. Denote P1=y1y2…yr, where y1=y and r≥4. Then, there is at least one edge yjyj+1 satisfying yjyj+1∉M and j∈2,3,…,r−1. Let G′′=G−yjyj+1+yyj+1. Obviously, G′′ is also a quasi-tree graph of order 2k with a perfect matching. By (1) and (2),(21)SEIaG′′−SEIaG=dGy+1adGy+1+2a2−dGyadGy−3a3=t+2at+2+2a2−t+1at+1−3a3>0,a contradiction with the choice of the graph G.
DenoteV1=u∈VTdTu=1,uy∈EG. Since G has a perfect matching, by Claim 4, it follows that V1|=0 or V1|=2.
IfV1|=0, then G≅QT22k. If V1|=2, then G≅QT12k. By (16), for k≥3, SEIaQT12k>SEIaQT22k. Therefore, G≅QT12k.
By Theorem3, Theorem 5 is obtained immediately.Theorem 5.
SupposeG is a quasi-tree graph of order 2k with a perfect matching, where k≥2, then for a>1,(22)SEIaG≥4k−1a2+2a,with equality if and only if G≅P2k.


## 5. Variable Sum Exdeg Indices of Unicyclic Graphs with Given Cycle Length

LetCn,l1 and Cn,l2 (as shown in Figure 4) denote the graph obtained from Cl by identifying its one vertex with the center vertex of Sn−l+1 and the graph obtained from Cl by identifying its one vertex with a pendant vertex of Pn−l+1, respectively.Figure 4
The graphsCn,l1 and Cn,l2.
(a)(b)Theorem 6.
LetU be an n-vertex unicyclic graph with cycle length l≤n−1. Then, for a>1,(23)SEIaU≤n−l+2an−l+2+n−la+2l−1a2,with equality only when U≅Cn,l1.Proof.
ChooseU such that U has the maximum SEIa for a>1. Suppose C is the only cycle in U.Claim 1.
There is at most one vertexu∈VC with dUu≥3 in U.
To the contrary, suppose that there exist two verticesx,y∈VC such that dUx≥dUy≥3. Thus, there exists one vertex z∈NUy, but z∉VC. It is evident that z∉NUx. Let U′=U−yz+xz. Then, C has no change and U′ is also an n-vertex unicyclic graph with cycle length l. By (1) and (2), it follows that(24)SEIaU′−SEIaU=dUy−1adUy−1+dUx+1adUx+1−dUyadUy−dUxadUx>0.a contradiction with the choice of the graph U.Claim 2.
Forv∉VC, dUv=1.
Assume, to the contrary, that there exists one vertexv∉VC with dUv=d≥2. Denoted by P=x1x2…xr (where v=x1 and xr∈VC) the path from v to C. Then NUv∩P=x2. Since v∉VC and dUv=d≥2, it follows that NUv\x2≠∅ and NUv\x2∩NUxr=∅. Denote NUv\x2=y1,y2,…ys, where s≥1. Let U′′=U−vy1,vy2,…,vys+xry1,xry2,…,xrys. Then, C has no change and U′′ is also an n-vertex unicyclic graph with cycle length l. By (1) and (2), it follows that(25)SEIaU′′−SEIaU=dUxr+sadUxr+s+a−dUxradUxr−s+1as+1>0,a contradiction again.
By Claims1 and 2, we have U≅Cn,l1.Theorem 7.
LetU be a unicyclic graph of order n with cycle length l≤n−1. Then, for a>1,(26)SEIaU≥2n−2a2+3a3+a,
with equality only whenU≅Cn,l2.Proof.
ChooseU such that U has the minimum SEIa for a>1. Suppose C is the only cycle in U.Claim 3.
U contains at most one pendant vertex.
Suppose thatU contains at least two pendant vertices. Let x,y∈VU be two pendant vertices. We denote by P=z1z2…zt (where x=z1, y=zt and t≥3) the path from x to y with minimum length. Then, there is 1<i<t, j∈1,2,…,i−1 such that dUzi≥3 and dUzj≤2. Obviously, zi−1∉NUy.
LetU′=U−zi−1zi+zi−1y. Since x∉VC and dUzi−1≤2, then zi−1∉VC. Thus C has no change and U′ is also an n-vertex unicyclic graph with cycle length l. By (1) and (2), it follows that(27)SEIaU′−SEIaU=dUzi−1adUzi−1+2a2−dUziadUzi−a<0,a contradiction with the choice of the graph U.
Sincel≤n−1, by Claim 3, U has exactly one pendant vertex. This implies U≅Cn,l2.


## 6. Variable Sum Exdeg Index of Unicyclic Graphs with Given Pendant Vertex

LetUn,p1 (as shown in Figure 5) be the graph obtained from Cn−p by identifying its one vertex with the center vertex of Sp+1.Figure 5
The graphUn,p1.LetUn,p2 be the n-vertex unicyclic graphs having p pendant vertices and degree sequence b+2,…,b+2︸n−b(n−p,b+1,…,b+1︸b(n−p)−p,1,…,1︸p, where b=⌊n/n−p⌋.Theorem 8.
LetU be an n-vertex unicyclic graph with p≥1 pendant vertices. Then, for a>1,(28)SEIaU≤p+2ap+2+2n−p−1a2+pa,the equality holds only when U≅Un,p1.Proof.
ChooseU such that U has the maximum SEIa for a>1.Claim 1.
There is at most one vertexu with dUu≥3 in U.
Assume that there exist two verticesx,y∈VU with dUy≥dUx≥3. Let P=x1x2,…,xr (where x=x1, y=xr) be the path from x to y with minimum length. Since dUx≥3, there exists a vertex z∈NUx\x2∪NUy. Let U′=U−xz+yz. Clearly, U′ is also an n-vertex unicyclic graph with p pendant vertices. In view of (1) and (2), it follows that(29)SEIaU′−SEIaU=dUx−1adUx−1dUy+1adUy+1−dUxadUx−dUyadUy>0,a contradiction with the choice of the graph U.
Sincep≥1, by Claim 1, we have U≅Un,p1.Theorem 9.
LetU be an n-vertex unicyclic graph with p≥1 pendant vertices. Then, for a>1,(30)SEIaU≥n−n−pbb+2ab+2+n−pb−pb+1ab+1+pa,where b=⌊n/n−p⌋, with equality if and only if U≅Un,p2.Proof.
ChooseU such that U has the minimum SEIa for a>1. Suppose C is the only cycle in U.Claim 2.
Ifxandy are two nonpendant vertices of U, then dUx−dUy≤1.
Assume that there are two verticesx,y∈VU with dUx−dUy|≥2. Suppose without loss of generality that dUx−2≥dUy≥2. Since dUx≥4, then there exist at least two vertices z1,z2∈NUx/VC. Furthermore, since U is a unicyclic graph, NUy∪y contains at most one of z1,z2. Set z∈z1,z2 and z∉NUy∪y. Let U′=U−xz+yz. Note that dU′y=dUy+1≥3 and dU′x=dUx−1≥3, so U is also a unicyclic graph with p pendant vertices. In view of (1) and (2), it follows that(31)SEIaU′−SEIaU=dUy+1adUy+1+dUx−1adUx−1−dUyadUy−dUxadUx<0,a contradiction with the choice of the graph U.
By Claim2, we can find that U has degree 1, k, or k+1, where k≥2. Hence(32)p+nk+nk+1=n.
SinceU is a unicyclic graph, then p≤n−3 and(33)p+knk+k+1nk+1=2n.
By (32) and (33), we have k=n/n−p+nk/n−p. By (32), nk≤n−p, hence k=⌊n/n−p⌋+1.
We also can get thatnk=⌊n/n−p⌋n−p−p,nk+1=n−⌊n/n−p⌋n−p.
So,U has the degree sequence(34)k+1,…,k+1︸nk+1,k,…,k︸nk,1,…,1︸p=b+2,…,b+2︸n−bn−p,b+1,…,b+1︸bn−p−p,1,…,1︸p,where b=⌊n/n−p⌋.


## 7. Results and Discussion

As one of the 148 topological indices that turned out good predictive properties,SEIa has a good correlation with the octanol-water partition coefficient. The mathematical properties of SEIa are worth studying [6] since this invariant can detect the desirable properties of chemical molecules. Therefore, our results may be used to predict the extremal properties of organic molecules.


## 8. Conclusions

In this work, we present the minimum and maximumSEIa (a>1) of quasi-tree graphs and quasi-tree graphs with perfect matchings and determine the minimum and maximum SEIa (a>1) of unicyclic graphs with given pendant vertices and cycle length. We will consider the bicyclic graphs with some graph parameters for further study.



---

*Source: 1317295-2020-08-26.xml*