# Ordering Acyclic Connected Structures of Trees Having Greatest Degree-Based Invariants

Authors: S. Kanwal; M.K. Siddiqui; E. Bonyah; T. S. Shaikh; I. Irshad; S. Khalid
Journal: Complexity
 (2022)

---

## Abstract

Being building block of data sciences, link prediction plays a vital role in revealing the hidden mechanisms that lead the networking dynamics. Since many techniques depending in vertex similarity and edge features were put forward to rule out many well-known link prediction challenges, many problems are still there just because of unique formulation characteristics of sparse networks. In this study, we applied some graph transformations and several inequalities to determine the greatest value of first and second Zagreb invariant,SK and SK1 invariants, for acyclic connected structures of given order, diameter, and pendant vertices. Also, we determined the corresponding extremal acyclic connected structures for these topological indices and provide an ordering (with 5 members) giving a sequence of acyclic connected structures having these indices from greatest in decreasing order.


---

## Body

## 1. Introduction

The process of exploring the junctions and connections of a tree-like network is called network topology determination, where chemical compounds’ entities of a complicated chemical system are represented by vertices in acyclic graphic structures. This area of research is a well growing idea in investigation of dynamic tree-like networks because of its wide range of continuously spanning applications in different emerging fields of research. Devotion of a big amount of exploring material in literature to tree-like networks has attached great importance to acyclic graphic structures. Main idea behind consideration of tree-like network is that very often the targeting approach to trees can further be implemented or its extension can be applied to study more general and advanced networking structures. Aim of this work is to provide readers a technique to guess behavior of chemical invariants for complicated network by an easiest one tree-like network.In this study, the term “graph” will always indicate a simple, finite, and undirected graph. In theoretical chemistry, topological indices are often used within the development of the two well-known relationships termed as quantitative structure property [1]. These descriptors are used to build the mathematical basis for relationship between molecular structure and physico-chemical properties. There are several topological indices exist in the literature. In a graph K, VK and EK are the sets of vertices and edges, respectively. Let dKs denote the degree of a vertex s.First time topological indices were used by Wiener launched them as, the Wiener invariant. Once having the favorable result of Wiener invariant, many other vertex degree- and edge degree-dependent invariants were proposed by several researchers, see details [2–4] that are given as follows:(1)WK=∑s,t⊆VKdKs,t,ℳ1K=∑s∈VKds2=∑st∈EKds+dt,M2K=∑st∈EKdsdt.The most studied and most applied index among all topological indices is the Randić index, defined by Randić [5]:(2)R−1/2K=∑st∈EKdsdt−1/2=∑st∈EK1dsdt,ℛαK=∑st∈EKdsdtα,χαK=∑st∈EKds+dtα.In 2004, Miličević et al. [6] redeveloped the Zagreb invariants using edge degrees and defined the 1st and 2nd reformulated Zagreb indices as follows:(3)EM1K=∑f∈EKdf2,EM2K=∑f∼ldfdl.Here,df=degf given by sum of degrees of end points of edge f decreased by 2 and f∼l shows that lines f and l are sharing a common node in K. Moreover, the extreme values of EM1K and EM2K were represented in [7, 8].In [9], authors put forward new graphic invariants defined below:(4)SKQ=∑ts∈EQdQt+dQs2,SK1Q=∑ts∈EQdQtdQs2.In 2012, Xu et al. [10] established some graph transformations that maximize or minimize the multiplicative sum Zagreb index of graphs and used these graph transformations to determine the extremal graphs from tree, unicyclic, and bicyclic graphs.Two years later, Ji et al. [8] extended the work of Xu et al. [10] for 1st reformulated Zagreb index. Shirdel et al. [11] put forward the hyper-Zagreb index which is a degree-based topological index given by(5)HMK=∑st∈EKds+dt2.In 2017, Gao et al. [12] used the same graph transformations as given in [8] to compute the similar results as computed in [8] but for the hyper-Zagreb index.The eccentricityeccs of s∈K is the farthest distance from s to any other vertex, i.e., eccs=maxt∈VKds,t. The value of the maximum eccentricity in a graph K is called the diameter of K, and it is denoted by diam(K). Two vertices s,t∈VK are the diametral vertices of K, for which the distance between the vertices s and t is equal to diamK and the smallest path between vertices s and t is the diametral path. A path denoted as Pm contains m number of vertices. A caterpillar, that is a tree of order 3 or more, holds the property removal of whose pendant vertices generate a path. Mahapatraa et al. [13] determined a new technique of finding link prediction called RSM index; idea behind this motivation is to increase the users on a network. Shang et al. [14] proposed the model of networks that provide a common explanation for community of regular and acyclic networks. Shang et al. [15] put forward the method taking into account heterogeneity of networks and performed in a better way than the existing link prediction algorithms. Huge collection of bounds is evaluated for acyclic and general graphic structures via Zagreb group invariants. Borovicanin et al. [16], in an attempt to take overview of existing literature regarding lower and upper bounds of Zagreb invariants, provided the readers with a broad survey of such well-known estimates. Noureen et al. [17] evaluated the maximum values of Zagreb invariants for acyclic chemical structures with certain parameters of segments and branching nodes. Ali et al. [17] provided readers with a big collection of results regarding largest and smallest values for the invariant 0αR, taking into consideration already explored results for certain values of α, e.g., α=−2,−1,−1/2,2,3. For further notations related to graph theory, we refer [18], and for networking dynamics, we refer [19, 20].Plan of work and methodology of this work are looking at the behavior (increase or decrease) of first two Zagreb invariants after swapping certain lines from one node to other. Increase in the value of these invariants lead us to acyclic tree-like structures with biggest value of aforementioned invariants. During this increase, these operations of swapping lines enabled us to give an ordering of tree-like structure having first, second, till fifth maximum value of considered invariants.


## 2. First Zagreb Invariant and Graph Transformations

In this section, we make use of some graph transformations introduce by Tomescu et al. [21] to compute the 1st Zagreb index for acyclic connected graphs of given diameter, order, and pendant vertices. These transformations are listed in Figure 1.Figure 1
τ1-transform applied to K.τ1-transform: let K be a nontrivial connected graph having vertices x1,y1∈K, such that Nx1=y1,x1,1,x1,2,…,x1,s and Ny1=x1,y1,1,y1,2,…,y1,t, where x1 and y1 have no common neighbors in K, s≥0 and t≥1. Let τ1K be the graph derived by deleting edges y1y1,1,y1y1,2,…,y1y1,t and attaching new lines x1y1,1,x1y1,2,…,x1y1,t. We say that τ1K=K′ is a τ1-transform of K (see Figure 1).Lemma 1.
Letτ1K=K′ be an acyclic connected graph derived from K by τ1−transform, as depicted in Figure 1; then,(6)M1τ1K>M1K,for any s,t≥1.Proof.
We havedτ1Kx1=dKx1+t>dKx1 and dτ1Kx1+dτ1Ky1=dKx1+dKy1=s+t+2. Also, dK′x1,i=dKx1,i and dK′y1,j=dKy1,j. By the definition of 1st Zagreb index, we obtain(7)M1K′−M1K=∑i=1sdK′x1,i+dK′x1−dKx1,i+dKx1+∑j=1tdK′y1,j+dK′x1−dKy1,j+dKy1+dK′x1+dK′y1−dKx1+dKy1=∑i=1sdK′x1,i+s+t+1−dKx1,i+s+1+∑j=1tdK′y1,j+s+t+1−dKy1,j+t+1+s+t+1+1−s+1+t+1=st+ts=2st>0⇒M1τ1K=M1K′>M1K.
Since the degree ofy1 decreases in τ1-transform, the degrees of the nodes x1,1,x1,2,…,x1,s and y1,1,y1,2,…,y1,t remain unchanged.Lemma 2.
LetK and τ2K=K′ be two acyclic connected graphs, as presented in Figure 2, where dKz1,u≥1. Then,(8)M1τ2K>M1K.for any s>1 and t≥1.Figure 2
τ2-transform applied to K.Proof.
SincedKx1<dτ2Kx1 and dτ2Ky1<dKy1, so we have(9)M1K′−M1K=∑i=1sdK′x1,i+dK′x1−dKx1,i+dKx1+∑j=1tdK′y1,j+dK′x1−dKy1,j+dKy1+dK′x1+dK′y1+dK′x1+dK′y1−dKx1+dKy1+dK′y1+dK′z1−dKy1+dKz1,M1K′−M1K=∑i=1sdK′x1,i+s+t+1−dKx1,i+s+1+∑j=1tdK′y1,j+s+t+1−dKy1,j+t+2+s+t+1+2−s+1+t+2+2+r+1−t+2+r+1=∑i=1st+∑j=1ts−1−t=st+ts−1−t=st+st−2t=2ts−1>0⇒M1τ2K=M1K′>M1K.
Hence, the result holds.Lemma 3.
Letτ3K=K′ be an acyclic connected graph obtained from K by applying τ3−transform, as depicted in Figure 3, where dKx1,y1=dτ3Kx1,y1≥2 and dKz1,u=dτ3Kz1,u≥0. If s>1 and t≥1, then(10)M1K′>M1K.Figure 3
τ3−transform applied to K.Proof.
Like previous lemma and by definition ofM1K, we obtain(11)M1K′−M1K=∑i=1sdK′x1,i+dK′x1−dKx1,i+dKx1+∑j=1tdK′y1,j+dK′x1−dKy1,j+dKy1+dK′x1+dK′v−dKx1+dKv+dK′w+dK′y1−dKw+dKy1+dK′y1+dK′z1−dKy1+dKz1=∑i=1sdK′x1,i+s+t+1−dKx1,i+s+1+∑j=1tdK′y1,j+s+t+1−dKy1,j+t+2+s+t+1+2−s+1+2+2+2−2+t+2+2+r+1−t+2+r+1=st+ts−1+t−t−t=2st−2t=2ts−1>0⇒M1τ3K=M1K′>M1K.
Hence, the proof is complete.Lemma 4.
Letτ4K=K′ be the graph derived from K after applying τ4−transform on K, as shown in Figure 4. For any s>r−1, we have(12)M1K′>M1K.Figure 4
τ4−transform applied to K.Proof.
SincedKx1,z1≥1. If dKx1,z1≥2, then dτ4Kx1+dτ4Kz1=s+1+r+1=s+r+2=dKx1+dKz1, and by definition of M1K, we have(13)M1K′−M1K=∑i=1sdK′x1,i+dK′x1−dKx1,i+dKx1+∑j=1r−1dK′z1,j+dK′z1−dKz1,j+dKz1+dK′z1,r+dK′x1−dKz1,r+dKz1+dK′x1+dK′w−dKx1+dKw+dK′y+dK′z1−dKy+dKz1=∑i=1sdK′x1,i+s+2−dKx1,i+s+1+∑j=1r−1dK′z1,j+r−dKz1,j+r+1+1+s+2−1+r+1+s+2+2−s+1+2+2+r−2+r+1=s1+r−1−1+s+3−r+2+1−1=2s−2r+2=2s−r+1>0⇒M1τ4K=M1K′>M1K.
IfdKx1,z1=1, then(14)M1K′−M1K=∑i=1sdK′x1,i+dK′x1−dKx1,i+dKx1+∑j=1r−1dK′z1,j+dK′z1−dKz1,j+dKz1+dK′z1,r+dK′x1−dKz1,r+dKx1+dK′x1+dK′z1−dKx1+dKz1=∑i=1sdK′x1,i+s+2−dKx1,i+s+1+∑j=1r−1dK′z1,j+r−dKz1,j+r+1+1+s+2−1+r+1+s+2+r−s+1+r+1=s1+r−1−1+s+3−r+2=2s−2r+2=2s−r+1>0⇒M1τ4K=M1K′>M1K.


### 2.1. Acyclic Connected Structures with GreatestM1 Invariant

First, we identify the extremal graphs among acyclic connected graphs or (trees) with1st Zagreb index and provide an ordering of these trees from greatest in decreasing order for 1st Zagreb index, see Figure 5.Figure 5
Acyclic connected graphsT having greatest M1.Theorem 1.
LetT be a set of acyclic connected graphs with p≥3 vertices and diameter of T is 2≤d≤p−1; then, M1T attains the maximum value only for T=Sp,p−d+1.Proof.
Applyingτ1−transform in Lemma 1 at nodes not related to diametral path of T, we conclude that, between p−vertex acyclic connected graphs T of diameter d, the maximum of M1T achieves exactly in the set of multistars ℳℒp1,p2,…,pd−1.
After applying transformations explained in Lemmas2, 3, and 4, we deduce that maximum of M1T attains only for p1=p−d,p2=p3=…=0, and pd−1=1, i.e., for Sp,p−d+1.Corollary 1.
(a) LetT be a set of acyclic connected graphs with order p, and we have(15)maxdT=lM1T>maxdT=mM1Tif 2≤l≤m≤p−1.
(b) Acyclic connected graphs with greatestM1T are(16)ℳℒp−d,0,…,0,1,ℳℒp−d−1,0,…,0,2,…,ℳℒp−d+12,0,…,0,p−d+12,in set of acyclic connected graphs T and having diameter d=3≤d≤p−2.Proof.
(a) This result follows from Lemma1; after applying many times τ1−transform, ℳℒp−m,0,…,0,1 reduces to ℳℒp−l,0,…,0,1.
(b) Using Lemmas1-3 in order to deduce this ordering, then we use Lemma 4 to multistars ℳℒs,0,…,0,t of order p, having s+t=p−d+1.Theorem 2.
For everyp>8, the acyclic connected graphs T possessing the greatest 1st Zagreb index are in the following order:(17)M1K1,p−1>M1ℬℒp−3,1>M1ℬℒp−4,2>M1Sp,p−3>M1ℬℒp−5,3.Proof.
The starK1,p−1 is a unique acyclic connected graph of diameter two, which, by Corollary 1, attains the maximum value of M1K. Another maximum value of M1K reaches for Sp,p−2=ℬℒp−3,1, which maximizes M1K in the set of acyclic connected graphs having diameter three. The next maximum values are attained by ℬℒp−4,2, which is corresponding to ℬℒp−3,1 for p=5 and by ℬℒp−5,3 in the class of acyclic connected graphs of diameter three, and the maximum of M1K is obtained by Sp,p−3 in the class of acyclic connected graphs of diameter four. We have(18)M1ℬℒp−4,2>M1Sp,p−3.
Since this inequality indicates that we can deriveℬℒp−4,2 from Sp,p−3 by a τ1−transform, it leads that, for every p≥6, the acyclic connected graphs holding maximum values of M1K are K1,p−1,ℬℒp−3,1 and ℬℒp−4,2. Next, we contrast M1ℬℒp−5,3 with M1Sp,p−3 to get the 4th term in the required series. We have(19)M1ℬℒp−5,3−M1Sp,p−3=p−5p−3+p+15−p−4p−2+p−1+7=28−p<0,which means that M1ℬℒp−5,3<M1Sp,p−3, for every p>8.
We also have(20)M1ℬℒp−5,3−M1ℳℒp−5,0,2=p−5p−3+p+15−p−5p−3+p−2+13​=4>0.
For everyp≥4, here ℳℒp−5,0,2 gets the next maximum value of M1K in the set of acyclic connected graphs with diameter four after Sp,p−3. After applying τ1−transform, we see that the acyclic connected graph ℳℒp−5,0,0,1 attaining maximum of M1K in the set of acyclic connected graphs with diameter five performs M1ℳℒp−5,0,0,1<M1ℳℒp−5,0,2, which terminates the proof.


### 2.2. Example

Now, we will see that, forp=10,(21)M1K1,p−1>M1BSp−3,1>M1BSp−4,2>M1Sp,p−3>M1BSp−5,3,where(22)M1K1,p−1=∑st∈EK1,p−1ds+dt,=91+9=90,M1BSp−3,1=∑st∈EBSp−3,1ds+dt,=71+8+8+2+2+1=76,M1BSp−4,2=∑st∈EBSp−4,2ds+dt,=61+7+7+3+21+3=66,M1Sp,p−3=∑st∈ESp,p−3ds+dt,=61+7+7+2+2+2+2+1=64,M1BSp−5,3=∑st∈EBSp−5,3ds+dt,=51+6+6+4+31+4=60.So, we are done.Table1 supports the ordering given in Theorem 2.Table 1
First Zagreb invariant for trees of order 12.
TM1TK1,11132BS9,1114BS8,2100S12,998BS7,390Theorem 3.
LetT be an acyclic connected graph having p≥5 nodes and t pendant nodes, where 3≤t≤p−2. Then,(23)M1T≤t2−3t+4p−4attains equality by the graph T=Sp,t.Proof.
First, we prove for vertexx of degree 1, attached to a node y; we have(24)M1T−M1T−x≤2tbound attained by the graph T=Sp,t and dy=t. We note that there exists a vertex z0∈Ny/x of degree dz0≥2 since in the other way T is a star having center y and t=p−1 pendant nodes, which conflict with the theorem. We obtain(25)M1T−M1T−x=dy+1−∑z∈Ny/xdy+dz−1−dy+dz.
Fordy−2 vertices, dz0≥2z∈Ny/x,z0, where dz≥1. It implies that(26)M1T−M1T−x=dy+1−dy+dz0−1−dy+dz0−dy−2dy+dz−1−dy+dz=2dy.
Sincedy≤t, this implies(27)M1T−M1T−x≤2t.
Equality attains, bydy=t, a vertex adjacent to y is of degree two, and the remaining nodes are pendants, i.e., T=Sp,t, and there is a vertex of Sp,t of degree t to which x is adjacent.
Using induction technique forp, for p=5, we have t=3 and S5,3=ℬℒ1,2, as shown in Figure 5, which is the only one acyclic connected graph with order five and three pendant nodes. Let p≥6, and assume that, for every acyclic connected graph of order p−1 and with t pendant nodes, the theorem is true, where 3≤t≤p−3. For end node x linked with y, now investigation of two subcases is done: (a) degree of y is 2 and (b) degree of y is at least 3.
(a) Here the unique nodez attached to y has dz≥2, which means(28)M1T−M1T−x=dz+2+3−dz+1=4.
In this situation,T−x has t pendant nodes. Using induction, for t≤p−3, we get M1T−x≤M1Sp−1,t, which attains equality by the graph T−x=Sp−1,t. In this situation,(29)M1T=M1T−x+4≤M1Sp−1,t+4=M1Sp,t,and equality is attained by the graph T−x=Sp−1,t and dy=dz=2, i.e., T=Sp,t. If t=p−2, order of T−x is p−1, having p−2 vertices of degree one, i.e., T−x is the star graph of order p deducing T=Sp,p−2=Sp,t.
(b) The graphT−x consists of p−1 nodes and t−1 pendant nodes if dy≥3. Then, by this property and using induction for T−x, we obtain(30)M1T≤M1T−x+2t≤M1Sp−1,t−1+2t=M1Sp,t.
Equality attained by the graph isT−x=Sp−1,t−1 and dy=t, i.e., T=Sp,t.


## 2.1. Acyclic Connected Structures with GreatestM1 Invariant

First, we identify the extremal graphs among acyclic connected graphs or (trees) with1st Zagreb index and provide an ordering of these trees from greatest in decreasing order for 1st Zagreb index, see Figure 5.Figure 5
Acyclic connected graphsT having greatest M1.Theorem 1.
LetT be a set of acyclic connected graphs with p≥3 vertices and diameter of T is 2≤d≤p−1; then, M1T attains the maximum value only for T=Sp,p−d+1.Proof.
Applyingτ1−transform in Lemma 1 at nodes not related to diametral path of T, we conclude that, between p−vertex acyclic connected graphs T of diameter d, the maximum of M1T achieves exactly in the set of multistars ℳℒp1,p2,…,pd−1.
After applying transformations explained in Lemmas2, 3, and 4, we deduce that maximum of M1T attains only for p1=p−d,p2=p3=…=0, and pd−1=1, i.e., for Sp,p−d+1.Corollary 1.
(a) LetT be a set of acyclic connected graphs with order p, and we have(15)maxdT=lM1T>maxdT=mM1Tif 2≤l≤m≤p−1.
(b) Acyclic connected graphs with greatestM1T are(16)ℳℒp−d,0,…,0,1,ℳℒp−d−1,0,…,0,2,…,ℳℒp−d+12,0,…,0,p−d+12,in set of acyclic connected graphs T and having diameter d=3≤d≤p−2.Proof.
(a) This result follows from Lemma1; after applying many times τ1−transform, ℳℒp−m,0,…,0,1 reduces to ℳℒp−l,0,…,0,1.
(b) Using Lemmas1-3 in order to deduce this ordering, then we use Lemma 4 to multistars ℳℒs,0,…,0,t of order p, having s+t=p−d+1.Theorem 2.
For everyp>8, the acyclic connected graphs T possessing the greatest 1st Zagreb index are in the following order:(17)M1K1,p−1>M1ℬℒp−3,1>M1ℬℒp−4,2>M1Sp,p−3>M1ℬℒp−5,3.Proof.
The starK1,p−1 is a unique acyclic connected graph of diameter two, which, by Corollary 1, attains the maximum value of M1K. Another maximum value of M1K reaches for Sp,p−2=ℬℒp−3,1, which maximizes M1K in the set of acyclic connected graphs having diameter three. The next maximum values are attained by ℬℒp−4,2, which is corresponding to ℬℒp−3,1 for p=5 and by ℬℒp−5,3 in the class of acyclic connected graphs of diameter three, and the maximum of M1K is obtained by Sp,p−3 in the class of acyclic connected graphs of diameter four. We have(18)M1ℬℒp−4,2>M1Sp,p−3.
Since this inequality indicates that we can deriveℬℒp−4,2 from Sp,p−3 by a τ1−transform, it leads that, for every p≥6, the acyclic connected graphs holding maximum values of M1K are K1,p−1,ℬℒp−3,1 and ℬℒp−4,2. Next, we contrast M1ℬℒp−5,3 with M1Sp,p−3 to get the 4th term in the required series. We have(19)M1ℬℒp−5,3−M1Sp,p−3=p−5p−3+p+15−p−4p−2+p−1+7=28−p<0,which means that M1ℬℒp−5,3<M1Sp,p−3, for every p>8.
We also have(20)M1ℬℒp−5,3−M1ℳℒp−5,0,2=p−5p−3+p+15−p−5p−3+p−2+13​=4>0.
For everyp≥4, here ℳℒp−5,0,2 gets the next maximum value of M1K in the set of acyclic connected graphs with diameter four after Sp,p−3. After applying τ1−transform, we see that the acyclic connected graph ℳℒp−5,0,0,1 attaining maximum of M1K in the set of acyclic connected graphs with diameter five performs M1ℳℒp−5,0,0,1<M1ℳℒp−5,0,2, which terminates the proof.


## 2.2. Example

Now, we will see that, forp=10,(21)M1K1,p−1>M1BSp−3,1>M1BSp−4,2>M1Sp,p−3>M1BSp−5,3,where(22)M1K1,p−1=∑st∈EK1,p−1ds+dt,=91+9=90,M1BSp−3,1=∑st∈EBSp−3,1ds+dt,=71+8+8+2+2+1=76,M1BSp−4,2=∑st∈EBSp−4,2ds+dt,=61+7+7+3+21+3=66,M1Sp,p−3=∑st∈ESp,p−3ds+dt,=61+7+7+2+2+2+2+1=64,M1BSp−5,3=∑st∈EBSp−5,3ds+dt,=51+6+6+4+31+4=60.So, we are done.Table1 supports the ordering given in Theorem 2.Table 1
First Zagreb invariant for trees of order 12.
TM1TK1,11132BS9,1114BS8,2100S12,998BS7,390Theorem 3.
LetT be an acyclic connected graph having p≥5 nodes and t pendant nodes, where 3≤t≤p−2. Then,(23)M1T≤t2−3t+4p−4attains equality by the graph T=Sp,t.Proof.
First, we prove for vertexx of degree 1, attached to a node y; we have(24)M1T−M1T−x≤2tbound attained by the graph T=Sp,t and dy=t. We note that there exists a vertex z0∈Ny/x of degree dz0≥2 since in the other way T is a star having center y and t=p−1 pendant nodes, which conflict with the theorem. We obtain(25)M1T−M1T−x=dy+1−∑z∈Ny/xdy+dz−1−dy+dz.
Fordy−2 vertices, dz0≥2z∈Ny/x,z0, where dz≥1. It implies that(26)M1T−M1T−x=dy+1−dy+dz0−1−dy+dz0−dy−2dy+dz−1−dy+dz=2dy.
Sincedy≤t, this implies(27)M1T−M1T−x≤2t.
Equality attains, bydy=t, a vertex adjacent to y is of degree two, and the remaining nodes are pendants, i.e., T=Sp,t, and there is a vertex of Sp,t of degree t to which x is adjacent.
Using induction technique forp, for p=5, we have t=3 and S5,3=ℬℒ1,2, as shown in Figure 5, which is the only one acyclic connected graph with order five and three pendant nodes. Let p≥6, and assume that, for every acyclic connected graph of order p−1 and with t pendant nodes, the theorem is true, where 3≤t≤p−3. For end node x linked with y, now investigation of two subcases is done: (a) degree of y is 2 and (b) degree of y is at least 3.
(a) Here the unique nodez attached to y has dz≥2, which means(28)M1T−M1T−x=dz+2+3−dz+1=4.
In this situation,T−x has t pendant nodes. Using induction, for t≤p−3, we get M1T−x≤M1Sp−1,t, which attains equality by the graph T−x=Sp−1,t. In this situation,(29)M1T=M1T−x+4≤M1Sp−1,t+4=M1Sp,t,and equality is attained by the graph T−x=Sp−1,t and dy=dz=2, i.e., T=Sp,t. If t=p−2, order of T−x is p−1, having p−2 vertices of degree one, i.e., T−x is the star graph of order p deducing T=Sp,p−2=Sp,t.
(b) The graphT−x consists of p−1 nodes and t−1 pendant nodes if dy≥3. Then, by this property and using induction for T−x, we obtain(30)M1T≤M1T−x+2t≤M1Sp−1,t−1+2t=M1Sp,t.
Equality attained by the graph isT−x=Sp−1,t−1 and dy=t, i.e., T=Sp,t.


## 3. Second Zagreb Invariant and Graph Transformations

In this section, we make use of some graph transformations introduced by Tomescu et al. [21] to compute the 2nd Zagreb index for acyclic connected graphs of given diameter, order. and pendant vertices. These graph transformations are described in Section 3.Lemma 5.
Letτ1K=K′ be an acyclic connected graph derived from K by τ1−transform, as depicted in Figure 1; then,(31)M2τ1K>M2K,for any s,t≥1.Proof.
We havedτ1Kx1=dKx1+t>dKx1 and dτ1Kx1+dτ1Ky1=dKx1+dKy1=s+t+2. By the definition of 2nd Zagreb index, we obtain(32)M2K′−M2K=∑i=1sdK′x1,idK′x1−dKx1,idKx1+∑j=1tdK′y1,jdK′x1−dKy1,jdKy1+dK′x1dK′y1−dKx1dKy1=∑i=1sdK′x1,is+t+1−dKx1,is+1+∑j=1tdK′y1,js+t+1−dKy1,jt+1+s+t+11−s+1t+1=st+ts−st=st>0⇒M2τ1K=M2K′>M2K.
Since the degree ofy1 decreases in τ1−transform, the degrees of the nodes x1,1,x1,2,…,x1,s and y1,1,y1,2,…,y1,t remain unchanged.Lemma 6.
LetK and τ2K=K′ be two acyclic connected graphs, as presented in Figure 2, where dKz1,u≥1. Then,(33)M2τ2K>M2K,for some s>r+1 and t≥1.Proof.
SincedKx1<dτ2Kx1 and dτ2Ky1<dKy1. So, we have(34)M2K−M2K=∑i=1sdK′x1,idK′x1−dKx1,idKx1=∑j=1tdK′y1,jdK′x1−dKy1,jdKy1+dK′x1dK′y1−dKx1dKy1+dK′y1dK′z1−dKy1dKz1=∑i=1sdK′x1,is+t+1−dKx1,is+1+∑j=1tdK′y1,js+t+1−dKy1,jt+2+s+t+12−s+1t+2+2r+1−t+2r+1=s1t+ts−1+2s+2t+2−st+2s+t+2+2r+2−rt+2r+t+2=st−rt−t=ts−r−1>0⇒M2τ2K=M2K′>M2K.
Hence, the result holds.Lemma 7.
Letτ3K=K′ be an acyclic connected graph obtained from K by applying τ3−transform, as depicted in Figure 3, where dKx1,y1=dτ3Kx1,y1≥2 and dKz1,u=dτ3Kz1,u≥0. If s>1 and t≥1, then(35)M2τ3K>M2K.Proof.
Like previous lemma and by definition ofM2K, we obtain(36)M2K′−M2K=∑i=1sdK′x1,idK′x1−dKx1,idKx1+∑j=1tdK′y1,jdK′x1−dKy1,jdKy1+dK′x1dK′v−dKx1dKv+dK′wdK′y1−dKwdKy1+dK′y1dK′z1−dKy1dKz1=∑i=1sdK′x1,is+t+1−dKx1,is+1+∑j=1tdK′y1,js+t+1−dKy1,jt+2+s+t+12−s+12+22−2t+2+2r+1−t+2r+1=s1t+ts−11+2t−2t−rt−r=2st−t−rt−t=t2s−r−2>0⇒M2τ3K=M2K′>M2K.
Hence, the proof is complete.Lemma 8.
Letτ4K be the graph derived from K after applying τ4−transform on K, as shown in Figure 4. For any s>r+1, we have(37)M2τ4K>M2K.Proof.
SincedKx1,z1≥1. If dKx1,z1≥2, then dτ4Kx1+dτ4Kz1=s+1+r+1=s+r+2=dKx1+dKz1, and by definition of M2K, we have(38)M2K′−M2K=∑i=1sdK′x1,idK′x1−dKx1,idKx1+∑j=1r−1dK′z1,jdK′z1−dKz1,jdKz1+dK′z1,rdK′x1−dKz1,rdKz1+dK′x1+dK′w−dKx1+dKw+dK′y+dK′z1−dKy+dKz1=∑i=1sdK′x1,is+2−dKx1,is+1+∑j=1r−1dK′z1,jr+dKz1,jr+1+1s+2−1r+1+s+22−s+12+2r−2r+1=s11+r−1−1+s+2−r+1+2−2=2s−2r+2=2s−r+1>0⇒M2τ4K=M2K′>M2K.
IfdKx1,z1=1, then(39)M2K′−M2K=∑i=1sdK′x1,idK′x1−dKx1,idKx1+∑j=1r−1dK′z1,jdK′z1−dKz1,jdKz1+dK′z1,rdK′x1−dKz1,rdKz1+dK′x1+dK′z1−dKx1+dKz1=∑i=1sdK′x1,is+2−dKx1,is+1+∑j=1r−1dK′z1,jr−dKz1,jr+1+1s+2−1r+1+s+2r−s+1r+1=s11+r−1−1+s+2−r+1+sr+2r−sr−s−r−1=s−r+1>0⇒M2τ4K=M2K′>M2K.


### 3.1. Acyclic Connected Graphs with GreatestM2

First, we identify the extremal graphic structures among acyclic connected graphs with2nd Zagreb index and provide an ordering of these acyclic connected graphs from greatest in decreasing order for 2nd Zagreb invariant (see Figure 6).Figure 6
Acyclic connected graphsT having greatest M2.Theorem 4.
LetT be a set of acyclic connected graphs with p≥3 vertices and diameter d of T is 2≤d≤p−1; then, M2T attains the maximum value only for T=Sp,p−d+1.Proof.
Applyingτ1−transform in Lemma 5 at nodes not related to diametral path of T, we conclude that, between p−vertex acyclic connected graphs T of diameter d, the maximum of M2T achieves exactly in the set of multistars ℳℒp1,p2,…,pd−1.
After applying transformations explained in Lemmas6, 7, and 8, we deduce that maximum of M2T attains only for p1=p−d,p2=p3=⋯=0, and pd−1=1, i.e., for Sp,p−d+1.Corollary 2.
(a) LetT be a set of acyclic connected graphs with order p; we obtain(40)maxdT=lM2T>maxdT=mM2Tif 2≤l≤m≤p−1.
(b) Acyclic connected graphs having diameterd with greatest M2T are in this decreasing sequence:(41)ℳℒp−d,0,…,0,1,ℳℒp−d−1,0,…,0,2,…,ℳℒp−d+1∖2,0,…,0,p−d+1∖2,where d=3≤d≤p−2.Proof.
(a) This result follows from Lemma5; after applying many times τ1−transform, ℳℒp−m,0,…,0,1 reduces to ℳℒp−l,0,…,0,1.
(b) Lemmas5, 6, and 7 are used in order to deduce this ordering, and then, we use Lemma 8 to multistars ℳℒs,0,…,0,t of order p, having s+t=p−d+1.Theorem 5.
For everyp>6, the acyclic connected graphs T possessing the greatest 2nd Zagreb index are in the following order (as shown in Figure 6):(42)M2K1,p−1>M2ℬℒp−3,1>M2ℬℒp−4,2>M2ℬℒp−5,3>M2Sp,p−3.Proof.
The starK1,p−1 is a unique acyclic connected graph of diameter two, which, by Corollary 2, attains the maximum value of M2K. Another maximum value of M2K reaches for Sp,p−2=ℬℒp−3,1, which maximizes M2K in the set of acyclic connected graphs having diameter three. The next maximum values are attained by ℬℒp−4,2, which is corresponding to ℬℒp−3,1, for p=5 and by ℬℒp−5,3 in the class of acyclic connected graphs of diameter three, and the maximum of M2K is obtained by Sp,p−3 in the class of acyclic connected graphs of diameter four. We have(43)M2ℬℒp−4,2>M2ℬℒp−5,3.
Since this inequality indicates that we can deriveℬℒp−4,2 from ℬℒp−5,3 by a τ4−transform, it leads that, for every p≥6, the acyclic connected graphs holding maximum values of M2K are K1,p−1,ℬℒp−3,1, and ℬℒp−4,2. Next, we contrast M2ℬℒp−5,3 with M2Sp,p−3 to get the 4th term in the required series. We have M2ℬℒp−5,3−M2Sp,p−3=p−5p−4+4p−4+12−p−4p−3+2p−3+6=4>0. which means that M2ℬℒp−5,3>M2Sp,p−3, for every p>4.
We also hold(44)M2Sp,p−3−M2ℳℒp−5,0,2=p−4p−3+2p−3+6−p−5p−4+2p−4+12=2p−6>0,for every p>6, where ℳℒp−5,0,2 gets the second maximum value of M2K in the set of acyclic connected graphs with diameter four after Sp,p−3. After applying τ1−transform, we see that the acyclic connected graph ℳℒp−5,0,0,1 attaining maximum of M2K in the set of acyclic connected graphs with diameter five perform M2ℳℒp−5,0,0,1<M2ℳℒp−5,0,2, which terminates the proof.


### 3.2. Example

Now, we will see that, forp=10,(45)M2K1,p−1>M2BSp−3,1>M2BSp−4,2>M2Sp,p−3>M2BSp−5,3,where(46)M2K1,p−1=∑st∈EK1,p−1dsdt=919=81,M2BSp−3,1=∑st∈EBSp−3,1dsdt=718+82+21=74,M2BSp−4,2=∑st∈EBSp−4,2dsdt=617+73+213=69,M2BSp−5,3=∑st∈EBSp−5,3dsdt=516+64+314=66,M2Sp,p−3=∑st∈ESp,p−3dsdt=617+72+22+11=62.So, we are done.Table2 is an illustration of Theorem 5.Table 2
Second Zagreb index for trees of order 12.
TM2TK1,11121BS9,1112BS8,2105BS7,3100S12,996Theorem 6.
LetT be an acyclic connected graph having p≥5 nodes and t pendant nodes, where 3≤t≤p−2. Then,(47)M2T≤t2−3t+4p−6,with equality for the structure T=Sp,t.Proof.
For end vertexx, linked to a node y, first, we prove(48)M2T−M2T−x≤2t.
T=Sp,t and dy=t. There exists z0∈Ny/x of degree dz0≥2; otherwise, T is a star having center y and t=p−1 pendant nodes, which conflict with the theorem. We obtain(49)M2T−M2T−x=dy.1−∑z∈Ny/xdy−1.dz−dy.dz.
Sincedz0≥2 and for left over dy−2 points z∈Ny/x,z0, where dz≥1, it implies that(50)M2T−M2T−x=dy.1−dy−1.dz0−dy.dz0−dy−2dy−1.dz−dy.dz=2dy.
We also getdy≤t since T−y includes dy acyclic connected graphs. Since 2≤dy≤t, this means(51)M2T−M2T−x≤2t.
Equality attains bydy=t, a vertex adjacent to y is of degree two, and the remaining nodes are pendant, i.e., T=Sp,t, and there is a vertex of Sp,t of degree t to which x is adjacent.
Making use of induction technique forp, p=5 gives t=3 and S5,3 is a bi-star with 1+2 pendant nodes, as shown in Figure 6, which is the only one acyclic connected graph with order five and three pendant nodes. Let p≥6, and assume that, for every acyclic connected graph of order p−1 and with t pendant nodes, the theorem is true, where 3≤t≤p−3. For end node x attached to node y, investigation of two subcases is made: (a) degree of y is 2 and (b) degree of y is at least 3.
(a) Here, the unique nodez attached to y has dz≥2, which means(52)M2T−M2T−x=2dz+2−dz=2+dz.
In this situation,T−x has t pendant nodes. Using induction, for t≤p−3, we get M2T−x≤M2Sp−1,t, which attains equality by the graph T−x=Sp−1,t. In this situation,(53)M2T=M2T−x+2+dz≤M2Sp−1,t+2+dz=t2−3t+4p−1−6+2+dz=t2−3t+4p−6−4+2+dz=Sp,t+dz−2and bound is attained for dz=2. Order of T−x is p−1, and cardinality of pendant nodes is p−2, for t=p−2, i.e., T−x is a star graph of order p, deducing T=Sp,p−2=Sp,t.
(b) The graphT−x consists of p−1 nodes and t−1 pendant nodes if dy≥3. Then, by this property and using induction for T−x, we obtain(54)M2T≤M2T−x+2t≤M2Sp−1,t−1+2t=M2Sp,t.
Equality attains by the graphT−x=Sp−1,t−1 and dy=t, i.e., T=Sp,t.
Since Shigehalli Kanabur invariants are scalar multiple of Zagreb invariants, so results related to ordering tree-like structures with respect to Zagreb invariants give parallel results forSK and SK1 invariants which just differ by positive scalar multiple.


## 3.1. Acyclic Connected Graphs with GreatestM2

First, we identify the extremal graphic structures among acyclic connected graphs with2nd Zagreb index and provide an ordering of these acyclic connected graphs from greatest in decreasing order for 2nd Zagreb invariant (see Figure 6).Figure 6
Acyclic connected graphsT having greatest M2.Theorem 4.
LetT be a set of acyclic connected graphs with p≥3 vertices and diameter d of T is 2≤d≤p−1; then, M2T attains the maximum value only for T=Sp,p−d+1.Proof.
Applyingτ1−transform in Lemma 5 at nodes not related to diametral path of T, we conclude that, between p−vertex acyclic connected graphs T of diameter d, the maximum of M2T achieves exactly in the set of multistars ℳℒp1,p2,…,pd−1.
After applying transformations explained in Lemmas6, 7, and 8, we deduce that maximum of M2T attains only for p1=p−d,p2=p3=⋯=0, and pd−1=1, i.e., for Sp,p−d+1.Corollary 2.
(a) LetT be a set of acyclic connected graphs with order p; we obtain(40)maxdT=lM2T>maxdT=mM2Tif 2≤l≤m≤p−1.
(b) Acyclic connected graphs having diameterd with greatest M2T are in this decreasing sequence:(41)ℳℒp−d,0,…,0,1,ℳℒp−d−1,0,…,0,2,…,ℳℒp−d+1∖2,0,…,0,p−d+1∖2,where d=3≤d≤p−2.Proof.
(a) This result follows from Lemma5; after applying many times τ1−transform, ℳℒp−m,0,…,0,1 reduces to ℳℒp−l,0,…,0,1.
(b) Lemmas5, 6, and 7 are used in order to deduce this ordering, and then, we use Lemma 8 to multistars ℳℒs,0,…,0,t of order p, having s+t=p−d+1.Theorem 5.
For everyp>6, the acyclic connected graphs T possessing the greatest 2nd Zagreb index are in the following order (as shown in Figure 6):(42)M2K1,p−1>M2ℬℒp−3,1>M2ℬℒp−4,2>M2ℬℒp−5,3>M2Sp,p−3.Proof.
The starK1,p−1 is a unique acyclic connected graph of diameter two, which, by Corollary 2, attains the maximum value of M2K. Another maximum value of M2K reaches for Sp,p−2=ℬℒp−3,1, which maximizes M2K in the set of acyclic connected graphs having diameter three. The next maximum values are attained by ℬℒp−4,2, which is corresponding to ℬℒp−3,1, for p=5 and by ℬℒp−5,3 in the class of acyclic connected graphs of diameter three, and the maximum of M2K is obtained by Sp,p−3 in the class of acyclic connected graphs of diameter four. We have(43)M2ℬℒp−4,2>M2ℬℒp−5,3.
Since this inequality indicates that we can deriveℬℒp−4,2 from ℬℒp−5,3 by a τ4−transform, it leads that, for every p≥6, the acyclic connected graphs holding maximum values of M2K are K1,p−1,ℬℒp−3,1, and ℬℒp−4,2. Next, we contrast M2ℬℒp−5,3 with M2Sp,p−3 to get the 4th term in the required series. We have M2ℬℒp−5,3−M2Sp,p−3=p−5p−4+4p−4+12−p−4p−3+2p−3+6=4>0. which means that M2ℬℒp−5,3>M2Sp,p−3, for every p>4.
We also hold(44)M2Sp,p−3−M2ℳℒp−5,0,2=p−4p−3+2p−3+6−p−5p−4+2p−4+12=2p−6>0,for every p>6, where ℳℒp−5,0,2 gets the second maximum value of M2K in the set of acyclic connected graphs with diameter four after Sp,p−3. After applying τ1−transform, we see that the acyclic connected graph ℳℒp−5,0,0,1 attaining maximum of M2K in the set of acyclic connected graphs with diameter five perform M2ℳℒp−5,0,0,1<M2ℳℒp−5,0,2, which terminates the proof.


## 3.2. Example

Now, we will see that, forp=10,(45)M2K1,p−1>M2BSp−3,1>M2BSp−4,2>M2Sp,p−3>M2BSp−5,3,where(46)M2K1,p−1=∑st∈EK1,p−1dsdt=919=81,M2BSp−3,1=∑st∈EBSp−3,1dsdt=718+82+21=74,M2BSp−4,2=∑st∈EBSp−4,2dsdt=617+73+213=69,M2BSp−5,3=∑st∈EBSp−5,3dsdt=516+64+314=66,M2Sp,p−3=∑st∈ESp,p−3dsdt=617+72+22+11=62.So, we are done.Table2 is an illustration of Theorem 5.Table 2
Second Zagreb index for trees of order 12.
TM2TK1,11121BS9,1112BS8,2105BS7,3100S12,996Theorem 6.
LetT be an acyclic connected graph having p≥5 nodes and t pendant nodes, where 3≤t≤p−2. Then,(47)M2T≤t2−3t+4p−6,with equality for the structure T=Sp,t.Proof.
For end vertexx, linked to a node y, first, we prove(48)M2T−M2T−x≤2t.
T=Sp,t and dy=t. There exists z0∈Ny/x of degree dz0≥2; otherwise, T is a star having center y and t=p−1 pendant nodes, which conflict with the theorem. We obtain(49)M2T−M2T−x=dy.1−∑z∈Ny/xdy−1.dz−dy.dz.
Sincedz0≥2 and for left over dy−2 points z∈Ny/x,z0, where dz≥1, it implies that(50)M2T−M2T−x=dy.1−dy−1.dz0−dy.dz0−dy−2dy−1.dz−dy.dz=2dy.
We also getdy≤t since T−y includes dy acyclic connected graphs. Since 2≤dy≤t, this means(51)M2T−M2T−x≤2t.
Equality attains bydy=t, a vertex adjacent to y is of degree two, and the remaining nodes are pendant, i.e., T=Sp,t, and there is a vertex of Sp,t of degree t to which x is adjacent.
Making use of induction technique forp, p=5 gives t=3 and S5,3 is a bi-star with 1+2 pendant nodes, as shown in Figure 6, which is the only one acyclic connected graph with order five and three pendant nodes. Let p≥6, and assume that, for every acyclic connected graph of order p−1 and with t pendant nodes, the theorem is true, where 3≤t≤p−3. For end node x attached to node y, investigation of two subcases is made: (a) degree of y is 2 and (b) degree of y is at least 3.
(a) Here, the unique nodez attached to y has dz≥2, which means(52)M2T−M2T−x=2dz+2−dz=2+dz.
In this situation,T−x has t pendant nodes. Using induction, for t≤p−3, we get M2T−x≤M2Sp−1,t, which attains equality by the graph T−x=Sp−1,t. In this situation,(53)M2T=M2T−x+2+dz≤M2Sp−1,t+2+dz=t2−3t+4p−1−6+2+dz=t2−3t+4p−6−4+2+dz=Sp,t+dz−2and bound is attained for dz=2. Order of T−x is p−1, and cardinality of pendant nodes is p−2, for t=p−2, i.e., T−x is a star graph of order p, deducing T=Sp,p−2=Sp,t.
(b) The graphT−x consists of p−1 nodes and t−1 pendant nodes if dy≥3. Then, by this property and using induction for T−x, we obtain(54)M2T≤M2T−x+2t≤M2Sp−1,t−1+2t=M2Sp,t.
Equality attains by the graphT−x=Sp−1,t−1 and dy=t, i.e., T=Sp,t.
Since Shigehalli Kanabur invariants are scalar multiple of Zagreb invariants, so results related to ordering tree-like structures with respect to Zagreb invariants give parallel results forSK and SK1 invariants which just differ by positive scalar multiple.


## 4. Conclusion

In chemical graph theory, in this work, we make use of some graphic transformations and several inequalities to determine the greatest value of first Zagreb invariant, second Zagreb invariant, andSK and SK1 invariants for acyclic connected structures of given order, diameter, and pendant vertices. Also, we determined the corresponding extremal acyclic connected structures for these chemical invariants and provided an ordering giving a sequence of acyclic connected structures having these indices from greatest in decreasing order. Calculations of topological invariant of any graphic structure are significant as it exhibits many of its chemical characteristics. However, much work still needs to be done in this area [22].



---

*Source: 3769831-2022-03-16.xml*