# On Acyclic Structures with Greatest First Gourava Invariant

Authors: Mariam Imtiaz; Maria Naseem; Misbah Arshad; Salma Kanwal; Maria Liaqat
Journal: Journal of Chemistry
 (2022)

---

## Abstract

Letξ be a simple connected graph. The first Gourava index of graph ξ is defined as GO1ξ=∑μη∈Eξdμ+dη+dμdη, where dμ indicates the degree of vertex μ. In this paper, we will find the upper bound of GO1ξ for trees of given diameter, order, size, and pendent nodes, by using some graph transformations. We will find the extremal trees and also present an ordering of these trees having this index in decreasing order.


---

## Body

## 1. Introduction

Topological index is very basic tool in chemical modeling. In molecular graph, atoms are considered as vertices and chemical bonds as edges. In short, the graph is a combination of vertices and edges. First chemical index was Wiener index introduced by Wiener [1] in 1947 to compare the boiling points of few alkanes isomers; he revealed that this index is highly agreed with the boiling point of molecules of alkanes. Later study on QSAR manifested that this index is also helpful to correlate with other quantities like density, critical point, and surface tension. The mathematical formula of this index is given as
(1)Wξ=∑μ,ηdξμ,η,where dξμ,η indicates the distance between the vertices μ and η in ξ. The most studied degree-based indices, i.e., Zagreb indices introduced by Gutman and Das [2], are defined as follows
(2)M1ξ=∑μ,η∈Vξdξμ2=∑μη∈Eξdξμ+dξη,M2ξ=∑μη∈Eξdξμdξη.Some properties about these indices are depicted in [3, 4]. The 1st and 2nd reformulated Zagreb indices were regenerated by Milic˘evic′ et al. [5] in terms of edge degree, defined as
(3)EM1ξ=∑f1∈Eξdf12,EM2ξ=∑f1~g1df1dg1.The1st and 2nd Gourava indices were presented by V. R. Kulli in 2017 [6]. These indices are defined as
(4)GO1ξ=∑μη∈Eξdμ+dη+dμdη,GO2ξ=∑μη∈Eξdμ+dηdμdη.A topological index is a mathematical formula, which has significant applications in chemical graph theory, because it is used as a molecular descriptor to investigate physical as well as chemical properties of chemical structure. Therefore, it is a powerful technique in avoiding high-cost and long-term laboratory experiments. There are3,000 topological invariants registered till now. All these indices have their applications in chemical graph theory. In these molecular descriptors, Gourava and hyper-Gourava invariants are used to find out the physical and chemical properties (such as entropy, acentric factor, and DHAVP) of octane isomers. The 1st and 2nd Gourava invariants highly correlate with entropy and acentric factor, respectively.In [7], the graph operations for Gourava index are presented. In our present study, we considered that all graphs are simple and connected. For any graph, the degree of a vertex is defined as the number of edges attached to it. The smallest degree of graph ξ is represented by δξ. The vertex in a graph whose degree is one is known as pendent vertex. The neighborhood of a vertex μ is the set of all nodes attached with μ, represented by Nμ. There are two types of neighborhood, open neighborhood and closed neighborhood. If Nμ includes all the other nodes except μ, then it is called open neighborhood, but if it includes the node μ, then it is called closed neighborhood. Closed neighborhood is defined as Nμ=Nμ∪μ (for further notations in graph theory, we refer [8]).Some bounds of reformulated Zagreb indices are given in [9]. In 2012, Xu and Das [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 among trees, unicyclic, and bicyclic graphs for multiplicative sum Zagreb index. Two years later, in 2014, Ji et al. [11] extended the work of Xu and Das [10] for the 1st reformulated Zagreb index. In 2017, Gao et al. [12] used the same graph transformations as given in [11] to compute the similar results as computed in [11] but for the hyper-Zagreb index.Tomescu and Kanwal [13] in 2013 introduced some graph transformations to compute the general sum-connectivity index for acyclic connected graphs of given diameter, order, and pendant vertices and determined the corresponding extremal trees and gave the ordering of trees with minimum general sum-connectivity index. Ilic′ et al. in 2011 [14] used some graph transformations to find the bounds for unicyclic and bicyclic graphs with respect to degree distance index. Liu et al. [15] analyzed the newly introduced chemical invariant termed as Mostar invariant for tree-like phenylenes and provided a detailed discussion for the obtained results. Liu et al. [16], provided an ordering of acyclic, bicyclic, and tricyclic structures with respect to recently introduced invariants Sombor and reduced Sombor invariants. In [17], Liu et al. determined some degree-based chemical invariants for octahedron networks. Qi et al. [18] put forward computations of several degree-based chemical invariants for rhombus-type silicate and oxide structures. In [19], the authors investigated several degree-based invariants for planar octahedron networks and made comparison of obtained numerical results. Hu et al. [20] analyzed certain distance-based invariants for chemical interconnection networks and analyzed their behavior.In this work, we are aimed to determine the acyclic structures having maximum values of first Gourava invariant and put forward acyclic structures attaining first five greatest values of first Gourava invariant. Plan of work and methodology behind attaining main results of this work is to apply certain edge swapping transformations to acyclic graphs and observe the behavior of first Gourava invariant. We will see that it increased for the resultant graph and eventually leads us to acyclic structures with the first five bigger values of above-mentioned invariant.


## 2. Gourava Index and Graph Transformations

In this section, we use certain graph transformations presented by Ji et al. [11]. Further, we will notice that these transformations increase the GO1 for trees. These transformations are narrated below.InB1‐transformation, let ξ be a nontrivial connected graph having vertices η,μ∈ξ, such that Nη1=μ1,η1,1,η1,2,⋯,η1,h and Nμ1=η1,μ1,1,μ1,2,⋯,μ1,f, where η1 and μ1 have no common neighbors in ξ, f≥0 and h≥1.Letξ′ be the graph obtained after applying B1−transformation, such that ξ′=ξ−η1η1,1,η1η1,2,⋯,η1η1,h+μ1η1,1,μ1η1,2,⋯,μ1η1,h as explained in Figure 1.Lemma 1.
Letξ be a connected graph with no cycle and ξ′ be a graph obtained after applying B1-transformation (as shown in Figure 1), and then, GO1B1ξ=GO1ξ′>GO1ξ for any f,h≥1.Proof.
From Figure1, dξ′=f+h+1 and dξ′η1=1. We can easily guess that degree of μ1 increases, while degree of η1 decreases after applying transformation, and all other vertices preserve their degrees.
(5)GO1ξ′−GO1ξ=∑i=1fdξ′μ1,i+dξ′μ1+dξ′μ1,idξ′μ1+∑j=1hdξ′η1,j+dξ′μ1+dξ,η1,jdξ′μ1+dξ,μ1+dξ′η1+dξ′μ1dξ′η1−∑i=1fdξμ1,i+dξμ1+dξμ1,idξμ1−∑j=1hdξη1,j+dξη1+dξη1,jdξη1−dξμ1+dξη1+dξμ1dξη1=∑i=1fdξ,μ1,i+dξ′μ1+dξ′μ1,idξ,μ1−dξμ1,i+dξμ1+dξμ1,idξμ1+∑j=1hdξ,η1,j+dξ,μ1+dξ,η1,jdξ,μ1−dξη1,j+dξη1+dξη1,jdξη1+dξ,μ1+dξ,η1+dξ′μ1dξ′η1−dξμ1+dξη1+dξμ1dξη1=∑i=1fdξ′μ1,i+f+h+1+f+h+1dξ′μ1,i−dξμ1,i+f+1+f+1dξμ1,i+∑j=1hdξ′η1,j+f+h+1+f+h+1dξ′η1,j−dξη1,j+h+1+h+1dξη1,j+f+h+1+1+f+h+1−f+1+h+1+f+1h+1=∑i=1fh+hdξμ1,i+∑j=1hf+fdξη1,j−fh=fh+hdξμ1,i+hf+fdξη1,j−fh=hfdξμ1,i+hfdξη1,j+hf=hfdξμ1,i+dξη1,j+1>0⇒GO1B1ξ=GO1ξ′>GO1ξLemma 2.
Letξ be an acyclic graph, and ξ′ is obtained after applying B2-transformation (as shown in Figure 2) where dξγ1,b1≥1; then,
(6)GO1B2ξ=GO1ξ′>GO1ξ,for any f>1 and h,ℓ≥1.Proof.
Heredξ′μ1,i=dξμ1,i, and dξ′η1,i=dξη1,i, and after transformation, dξ′μ1>dξμ1 and dξ′η1<dξη1.
(7)GO1ξ′−GO1ξ=∑i=1fdξ′μ1,i+dξ′μ1+dξ′μ1,idξ′μ1+∑j=1hdξ′η1,j+dξ′μ1+dξ′η1,jdξ′μ1+dξ′μ1+dξ′η1+dξ′μ1dξ′η1+dξ′η1+dξ′γ1+dξ′η1dξ′γ1−∑i=1fdξμ1,idξη1−dξμ1+dξη1+dξμ1dξη1−dξη1+dξγ1+dξη1dξγ1=∑i=1fdξ′μ1,i+dξ′μ1+dξ′μ1,idξ′μ1−dξμ1,i+dξμ1+dξμ1,idξμ1+∑j=1hdξ′η1,j+dξ′μ1+dξ′η1,jdξ′μ1−dξη1,j+dξη1+dξη1,jdξη1+dξ′μ1+dξ′η1+dξ′μ1dξ′η1−dξμ1+dξη1+dξμ1dξη1+dξ′η1+dξ′γ1+dξ′η1dξ′γ1−dξη1+dξγ1+dξη1dξγ1=∑i=1fdξ′μ1,i+f+h+1+f+h+1dξ′μ1,i−dξμ1,i+f+1+f+1dξμ1,i+∑j=1hdξ′η1,j+f+h+1+f+h+1dξ′η1,j−dξη1,j+h+2+h+2dξη1,j+f+h+1+2+2f+h+1−f+1+h+2+f+1h+2+2+ℓ+1+2ℓ+1−h+2+ℓ+1+h+2ℓ+1=∑i=1fh+hdξ′μ1,i+∑j=1hf−1+f−1dξ′η1,j+h−hf+−2h−hℓ=fh+hdξ′μ1,i+hf−1+f−1dξ′η1,j+h−hf+−2h−hℓ=hf+hf+hf−h+hf−h+h−hf−2h−hℓ=3hf−3h−hℓ=h3f−ℓ+3>0⇒GO1B2ξ=GO1ξ′>GO1ξ.Lemma 3.
Letξ be an acyclic graph and B3ξ=ξ′ is obtained after applying B3-transformation (as shown in Figure 3), where dξμ1,η1=dB3ξμ1,η1≥2 and dξγ1,g3=dB3γ1,g3≥0. If f>1, h,ℓ≥1, then,
(8)GO1B3ξ=GO1ξ′>GO1ξProof.
Like the previous lemma, we have(9)GO1ξ=∑i=1fdξ′μ1,i+dξ′μ1+dξ′μ1,idξ′μ1+∑j=1hdξ′η1,j+dξ′μ1+dξ′η1,jdξ′μ1+dξ′μ1+dξ′g1+dξ′μ1dξ′g1+dξ′g2+dξ′η1+dξ′g2dξ′η1+dξ′η1+dξ′γ1+dξ′η1dξ′γ1−∑i=1fdξμ1,i+dξμ1+dξμ1,idξμ1−∑j=1hdξη1,j+dξη1+dξη1,jdξη1−dξμ1+dξg1+dξμ1dξg1−dξg2+dξη1+dξg2dξη1−dξη1+dξγ1+dξη1dξγ1=∑i=1fdξ′μ1,i+dξ′μ1+dξ′μ1,idξ′μ1−dξμ1,i+dξμ1+dξμ1,idξμ1+∑j=1hdξ′η1,j+dξ′μ1+dξ′η1,jdξ′μ1−dξη1,j+dξη1+dξη1,jdξη1+dξ′μ1+dξ′g1+dξ′μ1dξ′g1−dξμ1+dξg1+dξμ1dξg1+dξ′g2+dξ′η1+dξ′g2dξ′η1−dξg2+dξη1+dξg2dξη1+dξ′η1+dξ′γ1+dξ′η1dξ′γ1−dξη1+dξγ1+dξη1dξγ1=∑i=1fdξ′μ1,i+f+h+1+f+h+1dξ′μ1,i−dξμ1,i+f+1+f+1dξμ1,i+∑j=1hdξ′η1,j+f+h+1+f+h+1dξ′η1,j−dξη1,j+h+2+h+2dξη1,j+f+h+1+2+2f+h+1−f+1+2+2f+1+2+2+4−2+h+2+2h+2+2+ℓ+1+2ℓ+1−h+2+ℓ+1+h+2ℓ+1=∑i=1fh+hdξ′μ1,i+∑j=1hf−1+f−1dξ′η1,j−hℓ−2h=fh+h+hf−1+f−1−hℓ−2h=fh+fh+fh−h+fh−h−hℓ−2h=4hf−4h−hℓ=hhf−ℓ+4>0⇒GO1B3ξ=GO1ξ′>GO1ξLemma 4.
Letξ be acyclic connected graph, and ξ′=B4ξ is obtained after applying B4-transformation(as shown in Figure 4) for any f>ℓ−1; we have GO1B4ξ=GOξ′>GO1ξ.Proof.
Sincedξμ1,γ1≥1, and if dξμ1,γ1≥2, then dξ′μ1+dξ′γ1=f+1+ℓ+1=dξμ1+dξγ1; now by using definition of GO1ξ, we have
(10)GO1ξ′−GO1ξ=∑i=1fdξ′μ1,i+dξ′μ1+dξ′μ1,idξ′μ1+∑j=1ℓ−1dξ′γ1,j+dξ′γ1+dξ′γ1,jdξ′γ1+dξ′γℓ+dξ′μ1+dξ′γℓdξ′μ1+dξ′μ1+dξ′g1+dξ′μ1dξ′g1+dξ′γ1+dξ′g2+dξ′γ1dξ′g2−∑i=1fdξμ1,i+dξμ1+dξμ1,idξμ1−∑j=1ℓ−1dξγ1,j+dξγ1+dξγ1,jdξγ1−dξγℓ+dξγ1+dξγℓdξγ1−dξμ1+dξg1+dξμ1dξg1−dξγ1+dξg2+dξγ1dξg2=∑i=1fdξ′μ1,i+dξ′μ1+dξ′μ1,idξ′μ1−dξμ1,i+dξμ1+dξμ1,idξμ1+∑j=1ℓ−1dξ′γ1,j+dξ′γ1+dξ′γ1,jdξ′γ1−dξγ1,j+dξγ1+dξγ1,jdξγ1+dξ′γℓ+dξ′μ1+dξ′γℓdξ′μ1−dξγℓ+dξγ1+dξγℓdξγ1+dξ′μ1+dξ′g1+dξ′μ1dξ′g1−dξμ1+dξg1+dξμ1dξg1+dξ′γ1+dξ′g2+dξ′γ1dξ′g2−dξγ1+dξg2+dξγ1dξg2=∑i=1fdξ′μ1,i+f+2+f+2dξ′μ1,i−dξ′μ1,i+f+1+f+1dξ′μ1,i+∑j=1ℓ−1dξ′γ1,j+ℓ+ℓdξ′γ1,j−dξγ1,j+ℓ+1+ℓ+1dξγ1,j+1+f+2+f+2−1+ℓ+1+ℓ+1+f+2+2+2f+2−f+1+2+2f+1+ℓ+2+2ℓ−ℓ+1+2+2ℓ+1=∑i=1f1+dξ′μ1,i+∑j=1ℓ−1−1−dξμ1,j+1+f+2+f+2−1+ℓ+1+ℓ+1+3−3=f2+−2ℓ−1+1+f+2+f+2−1+ℓ+1+ℓ+1+3−3=4f−4ℓ+4=4f−ℓ−1>0⇒GO1B4ξ=GO1ξ′>GO1ξ
Ifdξμ1,γ1=1, then
(11)GO1ξ′−GO1ξ=∑i=1fdξ′μ1,i+dξ′μ1+dξ′μ1,idξ′μ1+∑j=1ℓ−1dξ′γ1,j+dξ′γ1+dξ′γ1,jdξ′γ1+dξ′γℓ+dξ′μ1+dξ′γℓdξ′μ1+dξ′μ1+dξ′g1+dξ′μ1dξ′g1+dξ′γ1+dξ′g2+dξ′γ1dξ′g2−∑i=1fdξμ1,i+dξμ1+dξμ1,idξμ1−∑j=1ℓ−1dξγ1,j+dξγ1+dξγ1,jdξγ1−dξγℓ+dξγ1+dξγℓdξγ1−dξμ1+dξg1+dξμ1dξg1−dξγ1+dξg2+dξγ1dξg2=∑i=1fdξ′μ1,i+dξ′μ1+dξ′μ1,idξ′μ1−dξμ1,i+dξμ1+dξμ1,idξμ1+∑j=1ℓ−1dξ′γ1,j+dξ′γ1+dξ′γ1,jdξ′γ1−dξγ1,j+dξγ1+dξγ1,jdξγ1+dξ′γℓ+dξ′μ1+dξ′γℓdξ′μ1−dξγℓ+dξγ1+dξγℓdξγ1+dξ′μ1+dξ′g1+dξ′μ1dξ′g1−dξμ1+dξg1+dξμ1dξg1+dξ′γ1+dξ′g2+dξ′γ1dξ′g2−dξγ1+dξg2+dξγ1dξg2=∑i=1fdξ′μ1,i+f+2+f+2dξ′μ1,i−dξ′μ1,i+f+1+f+1dξ′μ1,i+∑j=1ℓ−1dξ′γ1,j+ℓ+ℓdξ′γ1,j−dξγ1,j+ℓ+1+ℓ+1dξγ1,j+1+f+2+f+2−1+ℓ+1+ℓ+1+f+2+2+2f+2−f+1+2+2f+1+ℓ+2+2ℓ−ℓ+1+2+2ℓ+1=∑i=1f1+dξ′μ1,i+∑j=1ℓ−1−1−dξμ1,j+1+f+2+f+2−1+ℓ+1+ℓ+1+3−3=f2+−2ℓ−1+1+f+2+f+2−1+ℓ+1+ℓ+1+3−3=4f−4ℓ+4=4f−ℓ−1>0⇒GO1B4ξ=GO1ξ′>GO1ξFigure 1
B1-tranformFigure 2
B2-transform.Figure 3
B3-transform.Figure 4
B4-transform.


## 3. Ordering Trees Having MaximumGO1

In this section, we identify the trees having maximum first Gourava index, and also, we give a sequence of these trees having first five largest values ofGO1.Theorem 5.
LetT∗ be a set of trees having order λ and diameter d∗, where λ≥3 and 2≤d∗≤λ−1. Then, GO1 is maximum value for T∗=Sλ,λ−d∗+1∗.Proof.
First, we applyB1-transformation to those vertices of T∗ which are other than diametral path, and we observe that maximum value of GO1 is obtained for MSλ1,λ2,⋯,λd∗−1. Then, we apply all those transformations which are explained above, and we conclude that the maximum value is acquired only for λ1=λ−d∗,λ2=λ3=⋯=0,λd∗−1=1 for Sλ,λ−d∗+1∗.Corollary 6.
(a) LetT∗ denotes the set of trees with order λ. Then,
(12)maxdiamT∗=ℓGO1T∗>maxdiamT∗=m′GO1T∗,where 2≤ℓ≤m′≤λ−1.
(b) Let the order of set of trees ofT∗ be λ with diameter 3≤d∗≤λ−2; then the greatest value of GO1T∗ for these graphs is in the following order: MSλ−d∗,0,⋯,0,1,MSλ−d∗−1,0,⋯,0,2,⋯,MSλ−d∗+1/2,0,⋯,0,λ−d∗+1/2.Proof.
We can achieveMSλ−ℓ,0,⋯,0,1 from MSλ−m′,0,⋯,0,1 by repeated use of first transformation (as described in Lemma 1).
(b) We use first three transformations (as explained in Lemmas1 to 3, and then, we use the fourth transformation to multistars MSg1,0,⋯,0,g2 with order λ where g1+g2=λ−d∗+1.Theorem 7.
Forλ>10, the trees having the greatest 1st Gourava index can be given in the following order (shown in Figure 5):
(13)GO1K1,λ−1>GO1BSλ−3,1>GO1BSλ−4,2>GO1Sλ,λ−3∗>GO1BSλ−5,3.Proof.
In the family of trees having diameter2, the star K1,λ−1 is the only tree which by above corollary possesses the greatest 1st Gourava index. The second maximum value of 1st Gourava index reaches for Sλ,λ−2∗=BSλ−3,1 for the trees having diameter 3. The third maximum value of this sequence can be obtained for BSλ−4,2 which also belongs to the class of trees having diameter 3. For λ=5, the BSλ−4,2 coincides with BSλ−3,1. The next graph in the class of trees with diameter 3 is BSλ−5,3. The next maximum value is obtained by Sλ,λ−3∗ which has diameter 4. We obtain
(14)GO1BSλ−4,2>GO1Sλ,λ−3∗.Figure 5
Five trees having maximum first Gourava index.Applyingτ1-transform to Sλ,λ−3∗, we obtain BSλ−4,2. It follows that for λ≥6, the order of trees possessing maximum value is GO1K1,λ−1>GO1BSλ−3,1>GO1BSλ−4,2. For the fourth term of this series, we have
(15)GO1BSλ−5,3−GO1Sλ,λ−3∗=λ−51+λ−4+λ−4+λ−4+4+4λ−4+34+1+4−λ−41+λ−3+λ−3+λ−3+2+2λ−3+2+2+4+1+2+2=λ−52λ−7+5λ−16+39−λ−42λ−5+3λ−7+8+5=2λ2−12λ+46−2λ2−10λ+26=210−λ<0This implies thatGO1BSλ−5,3<GO1Sλ,λ−3∗ for λ>10. So for λ>10, the fourth member in the above constructed sequence is Sλ,λ−3∗. For next member, we calculate
(16)GO1BSλ−5,3−GO1MSλ−5,0,2=λ−51+λ−4+λ−4+λ−4+4+4λ−4+34+1+4−λ−51+λ−4+λ−4+λ−4+2+2λ−4+2+3+6+21+3+3=λ−52λ−7+5λ−16+39−λ−52λ−7+3λ−6+11+14=2λ2−12λ+46−2λ2−14λ+54=2λ−4>0.Forλ>4, MSλ−5,0,2 gets the 2nd maximum value of GO1 in the set of trees of diameter 4. Applying 1st transformation (as described earlier) to MSλ−5,0,2, we get MSλ−5,0,0,1 which attains maximum value of 1st Gourava index in the set of trees of diameter 5 and MSλ−5,0,0,1<MSλ−5,0,2 which terminates the proof.For example, forλ=12, we see that
(17)GO1K1,λ−1>GO1BSλ−3,1>GO1BSλ−4,2>GO1Sλ,λ−3∗>GO1BSλ−5,3,which as a result verifies our main result of this work.
(18)GO1K1,λ−1=∑μη∈EK1,λ−1dμ+dη+dμdη=1111+1+11=25GO1BSλ−3,1=∑μη∈EBSλ−3,1dμ+dη+dμdη=91+10+10+10+2+20+2+1+2=226,GO1BSλ−4,2=∑μη∈EBSλ−4,2dμ+dη+dμdη=81+9+9+9+3+27+21+3+3=205,GO1Sλ,λ−3=∑μη∈ESλ,λ−3dμ+dη+dμdη=81+9+9+9+2+18+8+4+32+2+2+4+2+1+2=194,GO1BSλ−5,3=∑μη∈EBSλ−5,3dμ+dη+dμdη=71+8+8+8+4+32+31+4+4=190.Hence proved(19)GO1K1,λ−1>GO1BSλ−3,1>GO1BSλ−4,2>GO1Sλ,λ−3∗>GO1BSλ−5,3.Table1 provides certain trees Tλ∗ of order λ, along with their value of GO1.Theorem 8.
LetT∗ be a tree having order λ≥5 with α-leaf nodes, where 3≤α≤λ−2. Then,
(20)GO1T∗≤2α2−3α+4λ−5.
Equality holds ifT∗=Sλ,α∗.Proof.
First under the supposition of theorem, we prove that ifx′ is a pendant node attached to a vertex y′, then
(21)GO1T∗−GO1T∗−x≤4α.
Equality holds forSλ,α∗ and for dy′=α. Here, we notice that there exist a vertex ℓ0∈Ny′\x′ such that dℓ0≥2 since otherwise T∗ would be a star, which is against the supposition of theorem. Now,
(22)GO1T∗−GO1T∗=dy′+1+dy′−∑z∈Ny′x′dy′−1+dℓ+dy′−1dℓ−dy′+dℓ+dy′dℓ.
Sincedℓ0≥2, we have
(23)dy′−1+dℓ0+dy′−1dℓ0−dy′+dℓ0+dy′dℓ0≤3dy′−1−3dy′+2.
For the remainingdy′−2 nodes ℓ∈Ny′\x′,ℓ0, we conclude that
(24)dy′−1+dℓ+dy′−1dℓ−dy′+dℓ+dy′dℓ≤2dy′−1−2dy′+1.
This implies that(25)GO1T∗−GO1T∗=2dy′+1−dy′−1+dℓ0+dy′−1dℓ0−dy′+dℓ0+dy′dℓ0−dy′−2dy′−1+dℓ+dy′−1dℓ−dy′+dℓ+dy′dℓ≤2dy′+1−3dy′−1−3dy′+2−2dy′−1−2dy′+14dy′.
Sincedy′≤α,
(26)⇒GO1T∗−GO1T∗≤4α.
Equality holds ifdy′=α, one neighbor of y′ has degree two, while all the neighbor are leaf nodes, i.e., T∗=Sλ,α∗.
Now, the proof follows by induction onλ. For λ=5, we obtain α=3, and S5,3∗=BS∗1,2 is a single tree of order 5 having three pendant nodes.
Letα≥6 and suppose that the theorem is true for all the trees of order λ−1 having α-leaf nodes where 3≤α≤λ−3. Let x′ be the pendant node that is attached to node y′. Here, we examine two subcases:
(a)
Whendy′=2(b)
Whendy′≥3(a)
Fordy′=2, we have
(27)GO1T∗−GO1T∗−x′=dℓ+2+2dℓ+2+1+2−dℓ+1+dℓGO1T∗−GO1T∗−x′=6+dℓGO1T∗=6+dℓ+GO1T∗−x′GO1T∗≤6+dℓ+2α2−3α+4λ−1−5=2α2−3α+4λ−5−8+6+dℓ⟹GO1T∗≤Sλ,α∗+dℓ−2
Equality holds fordℓ=2. If α=λ−2, then T−x′ has λ−1 nodes and λ−2 pendent nodes, i.e., T∗−x′=κ1,λ−2 and T∗=Sλ,λ−2∗=Sλ,α.
(b)
Fordy′≥3, then T∗−x′ has λ−1 nodes and α−1 leaf nodes. Then, by induction, we obtain
(28)GO1T∗≤GO1T∗+4α≤Sλ−1,α−1∗+4α=Sλ,α∗
Equality holds ifT∗−x′=Sλ−1,α−1∗ and dy′=α, i.e., T∗=Sλ,α∗.Table 1
Comparison of different values ofGO1Tλ−1∗for λ=14.
Tλ−1∗GOTλ−1∗κ1,13351BS11,1318BS10,2291S14,11278BS9,3270



---

*Source: 6602899-2022-04-25.xml*