# On Trees with GreatestF−Invariant Using Edge Swapping Operations

Authors: Wenhu Wang; Adnan Aslam; Muhammad Ahsan Binyamin; Salma Kanwal; Iqra Irshad
Journal: Computational Intelligence and Neuroscience
 (2022)

---

## Abstract

TheF-index of a graph Q is defined as FQ=∑t∈VQdt3. In this paper, we use edge swapping transformations to find the extremal value of the F-index among the class of trees with given order, pendent vertices, and diameter. We determine the trees with given order, pendent vertices, and diameter having the greatest F-index value. Also, the first five maximum values of F index among the class of trees with given diameter are determined.


---

## Body

## 1. Introduction

Mathematical chemistry is providing effective and time-saving methods for evaluating the properties of chemical compounds without having to go through tedious laboratory experimentations. Topological indices are function maps that identify key computational and topological aspects of a structure and evaluate chemical compound properties without using quantum mechanics as final production [1]. The total π-electron energy E [2] of a molecule was found to be related to its thermodynamic stability that depends on the structure of a molecule that is its topology. Relationship between E and topology of a molecule was determined by its graphical structure [3]. Comparison was made between the original vertex degree-based indices and lately defined edge degree-dependent indices (termed as reformulated Zagreb indices), while relating the two versions of indices, the relation existing between the graph and its line graph was utilized. Yang et.al. [4] brought into consideration to researchers the relation between the subtree number index and the Weiner index in the class of spiro chains and polyphenyl hexagonal chains.In this paper, we consider only simple finite and connected graphs. In a graphQ, we denote its vertex set and edge set by VQ and EQ, respectively. Let dQp denotes the degree of a vertex p. The distance between two vertices p,t∈VQ is denoted by dp,t and is defined as the length of the shortest path joining them. For more undefined terminologies related to graph theory, we refer [5].The first topological index were proposed by Weiner [6] (namely, the Weiner index), while he was working on the boiling point of paraffin. The Weiner index is denoted by WQ and is defined as(1)WQ=∑p,t⊆VQdQp,t.Zagreb indices were introduced by Gutman et al. [2] that depend on degrees of nodes and are defined as(2)M1Q=∑p∈VQdp2M2Q=∑pt∈EQdpdt.These terms were recognized to be a measure of the extent of branching of the carbon atom skeleton of the underlying molecule. Later, its additive version was brought into kind attention to researchers in [7], which as expected, revealed more hidden chemical properties of chemical compounds. This index is named as the general sum connectivity index, given as(3)χαQ=∑pt∈EQdp+dtα.Furtulaet.al. [8] in 2015 introduced the F-index, also referred as the forgotten topological index, which is defined as(4)FQ=∑t∈VQdt3.This index is also a measure of branching and has same measure of predictability as that of the first Zagreb index. In case of the acentric factor and entropy, bothM1Q and FQ have a correlation coefficient greater than 0.95 [8].Ali et al. [9] put forward the survey of work done on the Randic index for certain values of α. Azari et al. [10] considered the forgotten topological index in detail and determined the bounds of this index in terms of other graphical parameters. They analyzed the relationship of this index with already exiting versions of Zagreb indices. Z. Che et al. [11] determined new bounds for the forgotten index in terms of graph irregularity, Zagreb indices, and many other existing graph invariants. Further they characterized the graphs attaining these bounds and proved that these newly attained bounds are sharper than the existing ones. Another version of the forgotten index namely the forgotten co-index was brought into attention by Ghalavand et al. [12]. The authors found bounds for this index and provided an ordering of graphs with respect to this index. Gutman et al. [13] provided a finite ascending sequence of the forgotten index for trees and moreover for graphs having some particular values of the cyclomatic number γ. Gutman et al. [14] proved two weighted inequalities of real nonnegative sequences and then used them to determine lower bounds of certain degree dependent indices.The main motivation behind this work is the idea practiced in [15], in which authors introduced some edge swapping operations on graph structures and analyzed the behavior of generalized sum connectivity descriptor. The authors found the decreasing behavior of the descriptor and provided the least five values of this descriptor for trees. Further they also provided the trees that attain these least values. In this work, making use of certain graph transformations that involve the swapping of edges from one node to another and contraction of edges, we have observed the behavior of the F-index. This enabled us to determine the decreasing sequence of values of F-invariant and the corresponding trees attaining these values. Novelty of work lies behind the fact that solving a research problem that is not solved already is always a good addition to the existing literature. Thus, this problem of determining members in a certain family of graph with first, second up to fifth extremal values has become good source of attraction to researchers.


## 2.F-Invariant under Certain Transformations

In this section, we first observe the increasing or decreasing behavior ofF-invariant under certain graph operations involving swapping of edges from one node to another. Our next results show that this descriptor exhibit increasing behavior.(5)α1−transform.LetQ be the connected tree and x1,y1∈VQ. For p≥0, t≥1, suppose Nx1=y1,x1,1,x1,2,…,x1,p and Ny1=x1,y1,1,y1,2,…,y1,t, where the vertices x1 and y1 have no common neighbors in Q. Let α1Q be the graph derived from Q by deleting edges y1y1,1,y1y1,2,…,y1y1,t and attaching new edges x1y1,1,x1y1,2,…,x1y1,t. We say that α1Q=Q′ is a α1−transform of Q (see Figure 1).Figure 1
α1−transform applied to Q.Lemma 1.
Letα1Q=Q′ be a tree derived from Q by α1-transform as depicted in Figure 1, then(6)Fα1Q>FQ.For anyp>1,t≥1.Proof.
Observe thatdQ′x1=dQx1+t>dQx1 and dQ′x1+dQ′y1=dQx1+dQy1=p+t+2.Consider that(7)FQ′−FQ=∑i=1pdQ′x1,i2+dQ′x12−dQx1,i2+dQx12+∑j=1tdQ′y1,j2+dQ′x12−dQy1,j2+dQy12+dQ′x12+dQ′y12−dQx12+dQy12=∑i=1pdQ′x1,i2+p+t+12−dQx1,i2+p+12+∑j=1tdQ′y1,j2+p+t+12−dQy1,j2+t+12+p+t+12+12−p+12+t+12=3ptt+p+2>0.
Theα1−transform decreases the degree of y1 by t and increases the degree of x1 by t, while the degrees of the nodes x1,1,x1,2,…,x1,p and y1,1,y1,2,…,y1,t remain unchanged.Lemma 2.
Letα2Q=Q′ be a tree derived from Q as depicted in Figure 2, where dQz1,u≥1. Then(8)Fα2Q>FQ.For anyp>1 and t≥1.Figure 2
α2−transform applied to Q.Proof.
SincedQx1<dα2Qx1 and dα2Qy1<dQy1, we have(9)FQ′−FQ=∑i=1pdQ′x1,i2+dQ′x12−dQx1,i2+dQx12+∑j=1tdQ′y1,j2+dQ′x12−dQy1,j2+dQy12+dQ′x12+dQ′y12−dQx12+dQy12+dQ′y12+dQ′z12−dQy12+dQz12=∑i=1p1+p+t+12−1−p+12+∑j=1t1+p+t+12−1−t+22+p+t+12+22−p+12+t+22+r+12+22−t+22+r+12=3tpt+p+2−t+3>0.
Hence, the result holds.Lemma 3.
Letα3Q=Q′ be a tree obtained from Q by applying α3-transform (see Figure 3), where dQz1,u=dα3Qz1,u≥0 and dQx1,y1=dα3Qx1,y1≥2. If t≥1 and s>1 then(10)Fα3Q>FQ.Figure 3
α3−transform applied to Q.Proof.
By definition ofFQ we get(11)FQ′−FQ=∑i=1pdQ′x1,i2+dQ′x12−dQx1,i2+dQx12+∑j=1tdQ′y1,j2+dQ′x12−dQy1,j2+dQy12+dQ′x12+dQ′v2−dQx12+dQv2+dQ′y12+dQ′z12−dQy12+dQz12+dQ′y12+dQ′w2−dQy12+dQw2=pp+t+12+1−p+12+tp+t+12+1−t+12+p+t+12+22−p+12+22+22+22−22+t+22+22+r+12−t+22−r+12=3tpp+t+2−t+3>0.
Hence the proof is complete.Lemma 4.
Letα4Qbe a tree obtained fromQafter applyingα4-transform (see Figure 4). For anyp,r≥0, we have(12)Fα4Q>FQ.Figure 4
α4−transform applied to Q.Proof.
IfdQx1,z1≥2, then dα4Qx1+dα4Qz1=dQx1+dQz1=p+r+2. Now by using the definition of F index, we have(13)FQ′−FQ=∑i=1pdQ′x1,i2+dQ′x12−dQx1,i2+dQx12+∑j=1r−1dQ′z1,j2+dQ′z12−∑j=1rdQ′z1,j2+dQ′z12+dQ′z1,r2+dQ′x12+dQ′x12+dQ′w2−dQx12+dQw2+dQ′y2+dQ′z12−dQy2+dQz12=pp+22+12−p+12−1+r−1r2+1−rr+12+1+1+p+22+p+22+22−p+12+22+22+r2−22+r+12=3pp+3−rr+1+2>0.


### 2.1. Greatest Value ofF−Index for Trees of Given Diameter

The multistar graph denoted byMSr1,r2,…,rd−1, where r1,rd−1≥1 and for 2≤j≤d−2, rj≥0, is the caterpillar involving a path a1,a2,…,ad−1 of length d−2 having rj pendant vertices that are adjacent to aj for 1≤j≤d−1. The diameter of MSr1,r2,…,rd−1 is equal to d, and can be derived by connecting the centers of K1,r1,K1,r2,…,K1,rd−1 with edges. A bistar graph of order r denoted by BSp,t, where p+t=r−2, is formed by connecting the central vertices of K1,p and K1,t by an edge. A tree that has diameter 3 is also a bistar. For integers r,t with 2≤t≤r−1, Sr,t is tree derived by connecting t−1 pendant vertices to the end node of the path Pr−t+1, with diameter dSr,t=r−t+1.Theorem 1.
LetTbe a tree onr≥3vertices and diameterd≥2. Then the maximum value ofFTis attained forT≅Sr,r−d+1.Proof.
Applyingα1-transform on the vertices that are not attached on the diametral path of T, we get that the maximum value of FT is attained in the class of multistars MSr1,r2,…,rd−1. Now applying the transformations presented in Lemma 2–Lemma 4, it follows that the maximum value of FT is attained if and only if r1=r−d,r2=r3=⋯=0 and rd−1=1. Hence T≅Sr,r−d+1.Corollary 1.
(i)
In the set of treesTonrvertices, we have(14)maxdT=iFT>maxdT=jFT.(ii)
for2≤i<j≤r−1.(iii)
In the set of treesT of order r and diameter d with 3≤d≤r−2, the graphs with the greatest FT value are (in this order) as follows:(15)MSr−d,0,…,0,1,MSr−d−1,0,…,0,2,…,MSr−d+12,0,…,0,r−d+12.Proof.
(i)
LetT be a tree on r vertices with diameter i. By Theorem 1 the maximum value of FT is attained for T≅Sr,r−i+1≅MSr−i,0,…,1. The result follows by applying many times α1-transform on MSr−i,0,…,1.(ii)
Applying Lemma1–Lemma 3 to T yields the multistar MSp,0,…,0,q with p+q=r−d+1. Now using Lemma 4 to MSp,0,…,0,q, we get the required ordering.Theorem 2.
For tree of orderr≥8, the maximum value of F-index is attained in the following order (see Figure 5).(16)FK1,r−1>FBSr−3,1>FBSr−4,2>FSr,r−3>FBSr−5,3.Figure 5
TreesT achieving greatest F−index.Proof.
LetT be tree of order r≥8. By Corollary 1, the maximum value of FT is achieved in the set of trees of diameter 2. It follows that the trees with the maximum value of FT is star K1,r−1. The second maximum is attained for Sr,r−2≅BSr−3,1 in the set of trees of diameter 3. The next maximum is reached by BSr−4,2 and BSr−5,3 in trees of diameter 3. Since BSr−3,1 can be obtained from BSr−4,2 by a α4 transformation, we get FK1,r−1>FBSr−3,1>FBSr−4,2. In the set of trees of diameter 4, the maximum value is attained by Sr,r−3. To get the fourth maximum value we compare FBSr−5,3 with FSr,r−3. We have(17)FBSr−5,3−FSr,r−3=r−51+r−42+r−42+16+317−r−41+r−32+r−32+4+8+5=−3r2+21r+12<0.
HenceFBSr−5,3<FSr,r−3 for every r≥8. Also,(18)FBSr−5,3−FMSr−5,0,2=r−51+r−42+r−42+16+317−r−5r−42+1+r−42+4+13+20=30>0.
This shows that the second maximum value ofF-index is achieved by MSr−5,0,2 after Sr,r−3 in the set of trees of diameter 4. Using a α1-transform, it is easy to see that MSr−5,0,0,1 reaches the maximum value in the set of trees of diameter 5 and FMSr−5,0,0,1<FMSr−5,0,2, which completes the proof.Example 1.
LetT be a tree on 10 vertices, then(19)FK1,10−1=∑uv∈EQ1,10−1d2u+d2v=912+92=738,FBS10−3,1=∑uv∈EBS10−3,1d2u+d2v=12+22+22+82+712+82=528,FBS10−4,2=∑uv∈EBS10−4,2d2u+d2v=212+32+32+72+612+72=378,FS10,10−3=∑uv∈ES10,10−3d2u+d2v=12+22+22+22+22+72+612+72=366,FBS10−5,3=∑uv∈E10−5,3d2u+d2v=312+42+42+62+512+62=288.
This shows that(20)FK1,10−1>FBS10−3,1>FBS10−4,2>FS10,10−3>FBS10−5,3.Theorem 3.
In the set of treesTof orderr≥5withtpendant vertices, where3≤t≤r−2, we have(21)FT≤t3−7t+8r−8.The above equality holds if and only ifT=Sr,t.Proof.
First we prove that ifx is a pendant vertex adjacent to y, then(22)FT−FT−x≤3t2−3t+2.
With equality holds if and only ifT=Sr,t and dy=t. Since 3≤t≤r−2, it follows that there exists a vertex z0∈Ny/x, such that dz0≥2. Otherwise T is a star having central vertex y. We obtain(23)FT−FT−x=dy2+1−∑z∈Ny/xdz2+dy−12−dz2+dy2.
Since,dz0≥2 and for the remaining dy−2 nodes z∈Ny/x,z0 , where dz≥1, we have(24)FT−FT−x=3dy2−3dy+2.
We also getdy≤t because T−y includes of dy trees. Now 2≤dy≤t gives(25)FT−FT−x≤3t2−3t+2,with equality holds if dy=t, the adjacent vertex of y has degree 2 and the remaining vertices are of degree 1. Hence T=Sr,t and x is adjacent to one of the vertex of Sr,t of degree t.
Now we use induction to prove the required result. Ifr=5, then t=3 and we have a bistar BS2,1 (see Figure 5), the only tree of order 5 having 3 pendant vertices. Let r≥6 and suppose the result is true for all trees of order r−1 and t pendant vertices, where 3≤t≤r−3. Let x be a pendant vertex adjacent to y, then we have two cases: (i) y has degree 2 and (ii) y is of degree at most 3.(i)
The only vertexz adjacent to y has degree dz≥2. Then(26)FT−FT−x=dz2+4+5−dz2+1=8.(ii)
In this case the graphT−x has t pendant vertices. Applying induction, for t≤r−3, we get FT−x≤FSr−1,t, with equality holds for T−x=Sr−1,t. It follows that(27)FT=FT−x+8≤FSr−1,t+8=FSr,t,(iii)
with equality holds forT−x=Sr−1,t. Therefore, we have T=Sr,t. If t=r−2, then T−x is a star with one vertex of degree 1. Hence, T=Sr,r−2=Sr,t.(iv)
LetT−x is of order r−1 with st−1 pendant vertices. If dy≥3, then by using induction on T−x, we get(28)FT≤FT−x+3t2−3t+2≤FSr−1,t−1+3t2−3t+2=FSr,t,
with equality holds forT−x=Sr−1,t−1 and dy=t. Hence T=Sr,t.


## 2.1. Greatest Value ofF−Index for Trees of Given Diameter

The multistar graph denoted byMSr1,r2,…,rd−1, where r1,rd−1≥1 and for 2≤j≤d−2, rj≥0, is the caterpillar involving a path a1,a2,…,ad−1 of length d−2 having rj pendant vertices that are adjacent to aj for 1≤j≤d−1. The diameter of MSr1,r2,…,rd−1 is equal to d, and can be derived by connecting the centers of K1,r1,K1,r2,…,K1,rd−1 with edges. A bistar graph of order r denoted by BSp,t, where p+t=r−2, is formed by connecting the central vertices of K1,p and K1,t by an edge. A tree that has diameter 3 is also a bistar. For integers r,t with 2≤t≤r−1, Sr,t is tree derived by connecting t−1 pendant vertices to the end node of the path Pr−t+1, with diameter dSr,t=r−t+1.Theorem 1.
LetTbe a tree onr≥3vertices and diameterd≥2. Then the maximum value ofFTis attained forT≅Sr,r−d+1.Proof.
Applyingα1-transform on the vertices that are not attached on the diametral path of T, we get that the maximum value of FT is attained in the class of multistars MSr1,r2,…,rd−1. Now applying the transformations presented in Lemma 2–Lemma 4, it follows that the maximum value of FT is attained if and only if r1=r−d,r2=r3=⋯=0 and rd−1=1. Hence T≅Sr,r−d+1.Corollary 1.
(i)
In the set of treesTonrvertices, we have(14)maxdT=iFT>maxdT=jFT.(ii)
for2≤i<j≤r−1.(iii)
In the set of treesT of order r and diameter d with 3≤d≤r−2, the graphs with the greatest FT value are (in this order) as follows:(15)MSr−d,0,…,0,1,MSr−d−1,0,…,0,2,…,MSr−d+12,0,…,0,r−d+12.Proof.
(i)
LetT be a tree on r vertices with diameter i. By Theorem 1 the maximum value of FT is attained for T≅Sr,r−i+1≅MSr−i,0,…,1. The result follows by applying many times α1-transform on MSr−i,0,…,1.(ii)
Applying Lemma1–Lemma 3 to T yields the multistar MSp,0,…,0,q with p+q=r−d+1. Now using Lemma 4 to MSp,0,…,0,q, we get the required ordering.Theorem 2.
For tree of orderr≥8, the maximum value of F-index is attained in the following order (see Figure 5).(16)FK1,r−1>FBSr−3,1>FBSr−4,2>FSr,r−3>FBSr−5,3.Figure 5
TreesT achieving greatest F−index.Proof.
LetT be tree of order r≥8. By Corollary 1, the maximum value of FT is achieved in the set of trees of diameter 2. It follows that the trees with the maximum value of FT is star K1,r−1. The second maximum is attained for Sr,r−2≅BSr−3,1 in the set of trees of diameter 3. The next maximum is reached by BSr−4,2 and BSr−5,3 in trees of diameter 3. Since BSr−3,1 can be obtained from BSr−4,2 by a α4 transformation, we get FK1,r−1>FBSr−3,1>FBSr−4,2. In the set of trees of diameter 4, the maximum value is attained by Sr,r−3. To get the fourth maximum value we compare FBSr−5,3 with FSr,r−3. We have(17)FBSr−5,3−FSr,r−3=r−51+r−42+r−42+16+317−r−41+r−32+r−32+4+8+5=−3r2+21r+12<0.
HenceFBSr−5,3<FSr,r−3 for every r≥8. Also,(18)FBSr−5,3−FMSr−5,0,2=r−51+r−42+r−42+16+317−r−5r−42+1+r−42+4+13+20=30>0.
This shows that the second maximum value ofF-index is achieved by MSr−5,0,2 after Sr,r−3 in the set of trees of diameter 4. Using a α1-transform, it is easy to see that MSr−5,0,0,1 reaches the maximum value in the set of trees of diameter 5 and FMSr−5,0,0,1<FMSr−5,0,2, which completes the proof.Example 1.
LetT be a tree on 10 vertices, then(19)FK1,10−1=∑uv∈EQ1,10−1d2u+d2v=912+92=738,FBS10−3,1=∑uv∈EBS10−3,1d2u+d2v=12+22+22+82+712+82=528,FBS10−4,2=∑uv∈EBS10−4,2d2u+d2v=212+32+32+72+612+72=378,FS10,10−3=∑uv∈ES10,10−3d2u+d2v=12+22+22+22+22+72+612+72=366,FBS10−5,3=∑uv∈E10−5,3d2u+d2v=312+42+42+62+512+62=288.
This shows that(20)FK1,10−1>FBS10−3,1>FBS10−4,2>FS10,10−3>FBS10−5,3.Theorem 3.
In the set of treesTof orderr≥5withtpendant vertices, where3≤t≤r−2, we have(21)FT≤t3−7t+8r−8.The above equality holds if and only ifT=Sr,t.Proof.
First we prove that ifx is a pendant vertex adjacent to y, then(22)FT−FT−x≤3t2−3t+2.
With equality holds if and only ifT=Sr,t and dy=t. Since 3≤t≤r−2, it follows that there exists a vertex z0∈Ny/x, such that dz0≥2. Otherwise T is a star having central vertex y. We obtain(23)FT−FT−x=dy2+1−∑z∈Ny/xdz2+dy−12−dz2+dy2.
Since,dz0≥2 and for the remaining dy−2 nodes z∈Ny/x,z0 , where dz≥1, we have(24)FT−FT−x=3dy2−3dy+2.
We also getdy≤t because T−y includes of dy trees. Now 2≤dy≤t gives(25)FT−FT−x≤3t2−3t+2,with equality holds if dy=t, the adjacent vertex of y has degree 2 and the remaining vertices are of degree 1. Hence T=Sr,t and x is adjacent to one of the vertex of Sr,t of degree t.
Now we use induction to prove the required result. Ifr=5, then t=3 and we have a bistar BS2,1 (see Figure 5), the only tree of order 5 having 3 pendant vertices. Let r≥6 and suppose the result is true for all trees of order r−1 and t pendant vertices, where 3≤t≤r−3. Let x be a pendant vertex adjacent to y, then we have two cases: (i) y has degree 2 and (ii) y is of degree at most 3.(i)
The only vertexz adjacent to y has degree dz≥2. Then(26)FT−FT−x=dz2+4+5−dz2+1=8.(ii)
In this case the graphT−x has t pendant vertices. Applying induction, for t≤r−3, we get FT−x≤FSr−1,t, with equality holds for T−x=Sr−1,t. It follows that(27)FT=FT−x+8≤FSr−1,t+8=FSr,t,(iii)
with equality holds forT−x=Sr−1,t. Therefore, we have T=Sr,t. If t=r−2, then T−x is a star with one vertex of degree 1. Hence, T=Sr,r−2=Sr,t.(iv)
LetT−x is of order r−1 with st−1 pendant vertices. If dy≥3, then by using induction on T−x, we get(28)FT≤FT−x+3t2−3t+2≤FSr−1,t−1+3t2−3t+2=FSr,t,
with equality holds forT−x=Sr−1,t−1 and dy=t. Hence T=Sr,t.


## 3. Conclusion

In this paper, our main focus is to obtain the greatest value ofF-index for trees of given order, diameter, and pendent vertices. Also, we determine the ordering of corresponding extremal trees for F-index. We make use of some graph transformations to determine the greatest value of F-index for trees of given order, diameter, and pendent vertices. These transformations involves contraction and swapping of pendant edges from one vertex to other resulting in increase in the value of the forgotten index. Using these transformations continuously on a graph lead us to the desired extremal graph with respect to the forgotten index. On the way of obtaining extremal graphs, we also obtained some other members having the second, third, fourth, and fifth maximum value of the forgotten index.



---

*Source: 8291974-2022-06-28.xml*