# On the First Three Extremum Values of Variable Sum Exdeg Index of Trees

Authors: Shu-Bo Chen; Syed Sheraz Asghar; Muhammad Ahsan Binyamin; Zahid Iqbal; Tayyeb Mahmood; Adnan Aslam
Journal: Complexity
 (2021)

---

## Abstract

For a graphG, its variable sum exdeg index is defined as SEIaG=∑xy∈EGadx+ady, where a is a real number other than 1 and dx is the degree of a vertex x. In this paper, we characterize all trees on n vertices with first three maximum and first three minimum values of the SEIa index. Also, we determine all the trees of order n with given diameter d and having first three largest values of the SEIa index.


---

## Body

## 1. Introduction

We start by defining some basic notions related to graph theory. All the graphs we consider in this article are finite, simple, and connected. LetG be a graph with vertex set VG and edge set EG. A tree T is a graph without any cycle. Let du denote the degree of a vertex u and be defined as the count of neighbors of u. A vertex of degree one is called pendent vertex. A path Pn is a defined on a sequence of vertices u0,u1,…,un with every vertex in the sequence adjacent to the vertex next to it. In particular, dv1=dv2=⋯=dvn−1=dvn=2 (unless n=1). Let Sn+2 and Sm+1 be the star graphs on n+2 and m+1 vertices, respectively. Denote Sm,n by the graph obtained by identifying one of the end vertices of Sn+2 with the central vertex of Sm+1. Also, Pn−k,k is a graph obtained by identifying the central vertex of Sn−k+1 with one of the end vertex of path Pk−1. The degree sequence of a graph G is denoted by DG, and if the degree sequence of G is d1,d2,…,dn, then we write DG=d1,d2,…,dn. Furthermore, DG=y1c1,y2c2,…,yncn means G has ci vertices of degree yi for i=1,2,…,n. For undefined terminologies and notations, we refer the reader to [1].A topological index is a numerical quantity derived from the graph of a molecule. It is well known that these indices are invariant under graph isomorphism. Topological index of a molecule determines many of its physical/chemical properties such as molecular volumes, electronic population, and energy volumes, see [2, 3], for details. A large number of topological indices have been defined through the years, and they are very well correlated with many physical/chemical properties of molecules [4–6]. For a molecular graph G, the variable sum exdeg index was proposed by Vukicevic [7] in 2011 to predict the octanol-water partition coefficient of certain compounds. It is denoted by SEIaG and is defined as(1)SEIaG=∑xy∈EGadx+ady,where a>0 is a real number other than 1. From the above definition, it can be seen that SEIaG=∑x∈VGdxadx. It follows from the definition that the value of the SEIa index of any two graphs with the same degree sequence is equal. Among the benchmark set of 102 descriptors proposed by the International Academy of Mathematical Chemistry, 148 discrete Adriatic indices, and 48 variable Adriatic indices, the descriptor SEI0.37 has the greatest coefficient of determination (namely, 0.99) for predicting the octanol-water partition coefficient of octane isomers [8]. Therefore, it is of interest to explore the mathematical properties of this index. For a>1, Vukicevic [7] determined the graphs with extremal values of the SEIa index among the classes of connected graphs (chemical graphs), unicyclic graphs (chemical unicyclic graphs), and trees (chemical trees). He also characterizes the extremal graphs with minimum (maximum) degree and trees having fixed number of vertices of degree 1. The variable sum exdeg polynomial was introduced by Yarahmadi and Ashrafi [9], and the effect of this polynomial under some graph operations was studied. They also studied the behavior of some nanotubes and nanotori using the variable sum exdeg polynomial. Using majorization technique, Ghalavand and Ashrafi [10] computed the graphs with extremal SEIaa>1 index value among the class of all n vertex unicyclic graphs and tree. They have also given a complete characterization of graphs with maximum SEIa (for a>1) value in the class of n-vertex tricyclic and bicyclic graphs. An alternate proof of some of the results in [10] is given by Ali and Dimitrov [11]. They also extended the results for tetracyclic graphs. Recently, S. Khalid and A. Ali [12] attempted to find the graphs with the extremal SEIaa>1 index value among the trees with prescribed vertex degrees. For more details on the mathematical properties of SEIa index, we refer the readers to [13–17].In this paper, first, we give an alternate proof to determine the trees with extremal values ofSEIaa>1 index. Using the same construction, we found the second and third maximum/minimum values of the SEIaa>1 index. Next, we characterize the chemical trees on n vertices with n−2=3d4+i, where i=0,1,2, having first and second maximum values of SEIaa>1. Finally, we found the trees with the first three largest SEIa index values in class of trees on n vertices and diameter d.


## 2. Extremal Values for Varibale Sum Exdeg Index of Trees

Lemma 1.
LetG be the graph with degree sequence DG=d1,d2,…,dn. Suppose there exists a pair dp,dq with dp≥dq+2 and let a new graph G′ be obtained from G by changing the pair dp,dq with dp−1,dq+1. If a>1, then SEIaG>SEIaG′.Proof.
Using the Mean value theorem and the definition of theSEIa index, we have(2)SEIaG−SEIaG′=dpadp−dp−1adp−1+dqadq−dq+1adq+1=dpan11+lna+adp−1−dqan21+lna−adq+1=1+lnadpan1−dqan2+adp−1−adq+1,where dp−1<n1<dp and dq<n2<dq+1. If a>1 and dp≥dq+2, then n1>n2, and from equation (2), we get SEIaG>SEIaG′.Lemma 2.
LetG be the graph with degree sequence DG=d1,d2,…,dn. Suppose there exists a pair dp,dq such that 2≤dq≤dp≤n−2, and let a new graph G′ be obtained from G by changing the pair dp,dq with dp+1,dq−1. If a>1, then SEIaG′>SEIaG.Proof.
Using the mean value theorem and the definition of theSEIa index, we have(3)SEIaG′−SEIaG=dp+1adp+1−dpadp+dq−1adq−1−dqadq,=dpan11+lna+adp+1−dqan21+lna−adq−1,=1+lnadpan1−dqan2+adp+1−adq−1.where dp<n1<dp+1 and dq−1<n2<dq. Since a>1 and dq≤dp, then n2<n1, and from equation (3), we get SEIaG′>SEIaGTheorem 1.
Leta>1 and T be a tree of order n. Then,(1)
SEIaT attains its maximum value iff T≅Sn(2)
SEIaT attains its 2nd maximum value iff T≅Sn−3,1(3)
SEIaT attains its 3rd maximum value iff T≅Sn−4,2(4)
SEIaT attains its minimum value iff T≅Pn(5)
SEIaT attains its 2nd minimum value iff T≅P2,n−2(6)
SEIaT attains its 3rd minimum value iff T≅P3,n−3Proof.
(1)
Suppose the degree sequence ofT is DT=d1,d2,…,dn. If T is not isomorphic to Sn, then there exists a pair dp,dq with 2≤dq≤dp≤n−2. Let T1 be a tree obtained from T by changing the pair dp,dq with dp+1,dq−1, then it follows from Lemma 2 that SEIaT1>SEIaT. We repeat the above procedure unless no pair dp,dq is left with 2≤dq≤dp≤n−2. In this way, we get a sequence of trees T1,T2,…,Tl such that SEIaT1<SEIaT2<⋯<SEIaTl−1<SEIaTl. Clearly, Tl≅Sn with degree sequence DTl=n−1,1n−1, and for any tree T not isomorphic to Sn, SEIaT<SEIaSn.(2)
Above construction shows thatSn is obtained from Tl by changing the pair dp,dq with dp+1,dq−1, where 2≤dq≤dp≤n−2. Observe that DTl−1=n−2,2,1n−2 and Tl−1≅Sn−3,1.(3)
Similarly, the degree sequenceDTl−2 of Tl−2 has two cases: DTl−21=n−3,2,2,1n−3 and DTl−22=n−3,3,1,1n−3. Note that DTl−22 can be obtained from DTl−21 by replacing the pair 2,2 of DTl−21 by 3,1. Clearly, Tl−22≅Sn−4,2 and Tl−21≅Pn−4,4. By Lemma 1, we have SEIaTl−22>SEIaTl−21. Hence, Tl−2≅Sn−4,2.(4)
LetT′ be a tree of order n with degree sequence DT′=d1′,d2′,…,dn′. Suppose T′ is not isomorphic to Pn; then, there exists a pair dp′,dq′ with dp′≥dq′+2. Let T1′ be a tree obtained from T′ by changing the pair dp′,dq′ with the pair dp′−1,dq′+1. Then, by Lemma 1, SEIaT′>SEIaT1′. Repeat the same operation until there is no pair dp′,dq′ such that dp′≥dq′+2 for all p,q. In this way, we get a sequence of trees T1′,T2′,T3′,…,Tm′ such that T1′≅Pn and SEIaT1′>SEIaT2′>SEIaT3′⋯>SEIaPn. Hence, for any tree T′ not isomorphic to Pn, SEIaT′>SEIaPn.(5)
Note that the degree sequence ofPn is DPn=2n−2,12. Now, Pn is obtained from Tm−1′ by changing the pair dp′,dq′ with the pair dp′−1,dq′+1, where dp′≥dq′+2. It is clear that the degree sequence of Tm−1′ is DTm−1′=3,2n−4,13 and Tm−1′≅P2,n−2.(6)
Similarly,DTm−2′ has the following cases: DTm−2′1=3,3,2n−6,14 or DTm−2′2=4,2,2n−6,14. Note that 3,3,2n−6,14 can be obtained from 4,2,2n−6,14 by replacing the pair 3,3 by the pair 4,2. Then, by Lemma 1, SEIaTm−2′2>SEIaTm−2′1. Hence, Tm−2′≅P3,n−3.
From the above theorem, we get the following corollary.Corollary 1.
(see [7]). Let T be a tree of order n. Then,(4)2a+2n−2a2≤SEIaT≤n−1a+n−1an−1.Theorem 2.
LetT be a chemical tree of order n and n−2=3d4+i, where i=0,1,2. If a>1, then we have(1)
SEIaT attains its maximum value iff DT=4d4,i+1,1n−d4−1(2)
SEIaT attains its 2nd maximum value iff DT=4d4−1,3,2,1n−d4−1 for i=0,DT=4d4−1,32,1n−d4−1 for i=1, and DT=4d4,22,1n−d4−2 for i=2Proof.
(1)
LetT be a chemical tree of order n and let DT=d1,d2,…,dn be its degree sequence. Suppose there exists a pair dp,dq such that 2≤dq≤dp≤3. We construct a graph T1 from T by changing the pair dp,dq with the pair dp+1,dq−1. Then, by Lemma 2, we have SEIaT1>SEIaT. We repeat the above procedure unless no pair dp,dq is left with 2≤dq≤dp≤3. In this way, we get a sequence of trees T1,T2,…,Tl such that SEIaT1<SEIaT2<⋯<SEIaTl−1<SEIaTl. Note that Tl has exactly one vertex of degree 2 or degree 3, while the remaining vertices are of degree 4 or degree 1. Let d1,d2,d3,andd4 be the vertices of degree 1, degree 2, degree 3, and degree 4, respectively; then,(5)d1+2d2+3d3+4d4=2n−1,d1+d2+d3+d4=n,d2+d3≤1.From the above equations, we get the following solutions:(1)
d2=d3=0, d1=n−d4, and d4=n−2/3 if n−2≡0mod3(2)
d2=1,d3=0, d1=n−d4−1, and d4=n−3/3 if n−2≡1mod3(3)
d2=0,d3=1, d1=n−d4−1, and d4=n−4/3 if n−2≡2mod3The solutions shows thatSEIaT attains its maximum value if and only if DT=4d4,i+1,1n−d4−1.(2)
Ifi=0, then from the proof of (2), it follows that DTl=4d4,1n−d4. One can see that DTl is obtained by DTl−1 by changing the pair dp,dq with the pair dp+1,dq−1, where 2≤dq≤dp≤3. So, we have DTl−1=4d4−1,3,2,1n−d4−1. If i=2, then DTl−1 has the following two cases: DTl−11=4d4−1,32,1n−d4−1 or DTl−12=4d4−1,3,22,1n−d4−2. Note that DTl−12=4d4−1,3,22,1n−d4−2 can be obtained from DTl−11=4d4−1,32,1n−d4−1 by replacing the pair 3,1 by the pair 2,2. Then, by Lemma 1, SEIaTl−11>SEIaTl−12. Hence, DTl−1=4d4−1,32,1n−d4−1. The case for i=3 follows in the same way.
From the above theorem, we get the following corollary.Corollary 2.
LetT be a chemical tree of order n and n−2=3d4+i, where i=0,1,2. Then, we have(6)SEIaT≤d4×4a4+i+1ai+1+n−d4−1a.In the next theorem, we characterize all the trees with the first three largestSEIa index values in class of trees with diameter d and order n.Theorem 3.
Leta>1 and T be a tree of order n with n≥3 and 2≤d≤n−1. Then,(1)
SEIaT attains its maximum value iff DT=n−d+1,2d−2,1n−d+1(2)
For3≤d≤n−3, SEIaT attains its 2nd maximum value iff DT=n−d,3,2d−3,1n−d+1(3)
Ford=n−4, SEIaT attains its third maximum value iff DT=33,2n−8,15 and for 3≤d≤n−5, SEIaT attains its 3rd maximum value iff DT=n−d−1,4,2d−3,1n−d+1Proof.
The cased=2 is trivial. Suppose that d≥3. Let Pd be a path of length d on T and v∈VT be a vertex of maximum degree on Pd. If DT≠n−d+1,2d−2,1n−d+1, then there exists a vertex u∈VT satisfying(a)
u∉Pd and du≥2(b)
u≠v, u∉Pd, and du≥3
First, suppose that there exists a vertexu∉Pd and du≥2. Choose u such that u is adjacent to exactly du−1 pendent vertices. Let the neighbors of u be u1,u2,…,uk=udu, and let Tu=T−uu1−uu2−⋯uuk+vu1+vu2+⋯+vuk.Claim.
:SEIaT<SEIaTu.
Ifdu≤dv in T, then the claim follows from Lemma 2. Suppose du>dv in T and let T′ be the tree obtained from T by changing the pair dv,du with the pair du,dv by pendent vertices (of u) transformation. Note that du≤dv in T′. Then, it is easy to see that SEIaT≤SEIaT′. Now, the tree Tu can be obtained from the tree T′ by applying the successive transformations and changing the pair dv,du with the pair dv+1,du−1. Thus, by Lemma 2, if follows SEIaT′<SEIaTu. Hence, for du>dv, we have SEIaT<SEIaTu. This proves our claim.
We repeat the above process until there is no vertex inT satisfying (a). Finally, we obtain a tree T1 which has no vertex satisfying (a) and SEIaT<SEIaT1.(1)
Next, we suppose that there is a vertexu satisfying (b) for T1 (instead of T). Let the neighbors of u be u1,u2,…,uk=udu, where u1 and u2 lie on the path Pd. Let Ti′=T1−uu3−⋯−uui+2+vu3+⋯+vui+2 for i=1,2,…,du−2. By Lemma 2, SEIaT1<SEIaT1′<SEIaT2′<⋯<SEIaTdu−2′. Repeating the above operation, we get a sequence of trees T1,T1′,…,Tl′ on n vertices and diameter d such that SEIaT1<SEIaT1′<SEIaT2′<⋯<SEIaTl′. Note that, in Tl′, there is no pair of distinct vertices with degree greater or equal to three. Clearly, DTl′=n−d+1,2d−2,1n−d+1. This proves (1).(2)
Suppose3≤d≤n−3. Since DTl′=n−d+1,2d−2,1n−d+1 and DTl′ is obtained from DTl−1′ by changing the pair dp,dq with the pair dp+1,dq−1, where n−3≥dp≥dq≥3, it is easy to see that DTl−1′ has two cases: DT1,l−1′=n−d,3,2d−3,1n−d+1 and DT2,l−1′=n−d,2d−1,1n−d+1. Note that DT2,l−1′ can be obtained from DT1,l−1′ by replacing the pair 3,1 by the pair 2,2. Then, by Lemma 1, SEIaT2,l−1′<SEIaT1,l−1′. This proves (2).(3)
In the similar way, we getDT1,l−2′=n−d−1,4,2d−3,1n−d+1 for 3≤d≤n−5 and DT2,l−2′=n−d−1,32,2d−4,1n−d+1=33,2n−8,15 for d=n−4. Since DT2,l−2′ can be obtained from DT1,l−2′ by replacing the pair 4,2 by the pair 3,3, by Lemma 1, SEIaT2,l−2′<SEIaT1,l−2′. It follows that DTl−2′=33,2n−8,15 for d=n−4 and DTl−2′=n−d−1,4,2d−3,1n−d+1. This proves (3).
A vertexv∈VT is called central vertex if ev=r. Every tree T has either one or two central vertices. If d=2r, then the tree T has just one central vertex, and if d=2r−1, then T has two central vertices. If we choose a tree with given radius r and d=2r−1, then we get the following result.Theorem 4.
Leta>1 and T be a tree of order n with n≥3 and 2≤r≤n/2. Then,(1)
SEIaT attains its maximum value iff DT=n−2r+2,22r−3,1n−2r+2(2)
For2≤r,n−2/2, SEIaT attains its 2nd maximum value iff DT=n−2r+1,3,22r−4,1n−2r+2(3)
Forr=n−3/2≥3, SEIaT attains its 3rd maximum value iff DT=33,2n−8,15 and for 2≤r<n−3/2, and SEIaT attains its 3rd maximum value iff DT=n−2r,4,22r−4,1n−2r+1


## 3. Conclusion

In this paper, we have considered the variable sum exdeg index and studied its mathematical properties. Fora>1, we have characterized a class of trees having order n and first three maximum/minimum values of the SEIa index. Also, we determine all the trees of order n with given diameter d and having first three largest values of the SEIa index. However, for 0<a<1, it remains an open problem to find the trees which have the first three maximum/minimum values of the variable sum exdeg index.



---

*Source: 6491886-2021-05-13.xml*