# On Vertex Degree-Based Topological Indices for Fixed Branching Vertices of Trees

Authors: Muzamil Hanif; Akhlaq Ahmad Bhatti; Muhammad Javaid; Md Nur Alam
Journal: Journal of Chemistry
 (2022)

---

## Abstract

The Gourava indices and hyper-Gourava indices are graph invariants, related to the degree of vertices of a graphG. Let Tn,b denote the collection of all chemical trees with n vertices where b denotes the number of branching vertices, 1≤b<n−2/2. In the current paper, maximum value for the abovementioned topological indices for different classes 1Tn,b and 2Tn,b of Tn,b is determined and the corresponding extremal trees are characterized.


---

## Body

## 1. Introduction

In this paper, we only consider simple, finite, and connected graphs. LetG be a simple graph of order n with vertex set VG=vi,i=1,2,3,.⋯,n and edge set EG=ej,j=1,2,3,.⋯,m. Let NuG be the neighborhood set of the vertex u in graph G. The number of adjacent vertices to a vertex u is said to be its degree, and it is denoted by du. The adjacency of two vertices u and v is denoted by u∼v. In a graph G, the vertices of degree one and the degree greater or equal to three are known as pendent (leaf) and branching vertices, respectively. A pendent vertex u is said to be a starlike pendent vertex if it is connected to a branching vertex v. Let Pn and Sn be the path and star graph of order n, respectively. A path which contains single pendent vertex is known as pendent path whereas if both ending vertices are branching in a path, then it is known as internal path [1]. A vertex degree-based topological index is a function TI^:Tn,b⟶ℝ induced by numbers φi,ji,j∈ϒ, defined for every tree T∈Tn,b as [2]
(1)TI^T=∑i,j∈ϒϱi,jTφi,j,where ϒ=i,j∈ℕ×ℕ:1≤i≤j≤4, and ϱi,j be the number of edges of vertices having degrees i and j.Topological indices are studied intensively in recent years and among the oldest and the most studied being the first and second Zagreb indicesM1G and M2G, respectively. In 1972, Gutman and Trinajstić defined the first and second Zagreb indices as [3, 4]
(2)M1G=∑v∈VGdv2G,M2G=∑u∼vduGdvG.The first Zagreb index is also defined as [5]
(3)M1G=∑u∼vduG+dvG.For the minimum first Zagreb index, trees have been characterized with respect to a fixed number of pendent vertices by Gutman and Goubko [6, 7]. Lin [8] maximized and minimized the first Zagreb index of the trees with respect to a fixed number of segments. After that, Borovićanin et al. [9–11] characterized certain classes of trees with maximum and minimum Zagreb indices with a fixed number of segments or branching vertices. In 2013, the upper bounds on the multiplicative Zagreb indices of Cartesian product, the join, composition, corona product, and disjunction of graphs have been derived by Das et al. [12]. In 2016, Das et al. [13] established some upper and lower bounds on the first Zagreb index of graphs and trees in terms of irregularity index, a number of vertices, and maximum degree and have characterized the extremal graphs. In 2016, the relations among Zagreb polynomials on three graph operators have been discussed by Bindusree et al. [14]. After that in 2019, Aykaç et al. [15] established first Zagreb index, second Zagreb index, first multiplicative Zagreb index, second multiplicative Zagreb index, first Zagreb coindices index, second Zagreb coindices index, first multiplicative Zagreb coindices index, and second multiplicative Zagreb coindices index of Γℤp2×ℤq2. Recently, Noreen et al. [1] characterized the n-vertex trees for maximum Zagreb indices with a fixed number of segments or branching vertices. For more details, see [1, 3, 4, 6, 7, 9–11, 16–26].In 2011, Azari and Iranmanesh [27] defined the generalized Zagreb index of graphs as
(4)Mα,βG=∑u∼vduGαdvGβ+duGβdvGα,∀α,β∈ℕ.Motivated by the first and second Zagreb indices and their various applications in the different disciplines, Kulli [28] defined the first Gourava index of a graph G as
(5)GO1G=∑u~vduG+dvG+duGdvG.Then, by motivation of the generalized Zagreb index and the first Gourava index, Kulli defined the second Gourava index as [28]
(6)GO2G=∑u~vduG+dvGduGdvG,which is also written in the form of generalized Zagreb index as
(7)GO2G=∑u∼vduG2dvG+duGdvG2,and computed the first and second Gourava indices, the multiplicative first and second Gourava indices, and general multiplicative first and second Gourava indices of armchair polyhex and zigzag-edge polyhex nanotubes. After that, Kulli defined first and second hyper-Gourava indices as [29]
(8)HGO1G=∑u~vduG+dvG+duGdvG2,(9)HGO2G=∑u∼vduG+dvGduGdvG2,and computed the first and second hyper-Gourava indices of HC5C7p,q,SC5C7p,q nanotubes. In 2021, Aftab et al. [30] computed the different topological indices such as the first and second Gourava indices and the first and second hyper-Gourava indices of subdivided hexagonal network, subdivided polythiophene network, subdivided honeycomb network, and subdivided backbone DNA network.The abovementioned indices have good correlation with physical properties of chemical compounds like entropy (S), acentric factor (AcentFac), and standard enthalpy of vaporization (DHVAP) of octane isomers.GO1 index correlates highly with entropy, and the correlation coefficient is r=0.9644924. Also, GO1 index has good correlation (r>0.9) with acentric factor and (r>0.8) with the standard enthalpy of vaporization. GO2 index correlates highly with acentric factor, and the correlation coefficient is r=0.9644924. Also, GO2 index has good correlation (r>0.9) with entropy and (r>0.75) with the standard enthalpy of vaporization. HGO1 index correlates highly with acentric factor, and the correlation coefficient is r=0.9554303. Also, HGO1 index has good correlation (r>0.9) with entropy and (r>0.75) with the standard enthalpy of vaporization. HGO2 index has good correlation (r>0.85) with entropy, (r>0.75) with acentric factor, and (r>0.6) with the standard enthalpy of vaporization. For more detail about the fitted models for the abovementioned indices, see [31].It is noted that for anyT∈Tn,n−2/2, it contains only vertices of degree one and three. So we let 1Tn,b,1≤b<n−2/3 and 2Tn,b,n−2/3≤b<n−2/2 be two subclasses of Tn,b with degree sequences 4,4,⋯,4⏟b,2,2,⋯,2⏟n−3b−2,1,1,⋯,1⏟2b+2 and 4,4,⋯,4⏟n−2b−2,3,3,⋯,3⏟3b−n+2,1,1,⋯,1⏟n−b, respectively. Let ViG be the number of vertices of degree i,1≤i≤4 in G. For chemical trees, the following relations are well known, where 1≤j≤4 and Δ=4.
(10)2ϱj,j+∑i=1i≠jΔϱj,i=jVj,(11)∑1≤i≤j≤Δϱi,j=n−1.From (10), we have following system of equations:
(12)2ϱ1,1+ϱ1,2+ϱ1,3+ϱ1,4=V1,(13)ϱ2,1+2ϱ2,2+ϱ2,3+ϱ2,4=2V2,(14)ϱ3,1+ϱ3,2+2ϱ3,3+ϱ3,4=3V3,(15)ϱ4,1+ϱ4,2+ϱ4,3+2ϱ4,4=4V4.


## 2. Main Result

Let1Tmax∈1Tn,b and 2Tmax∈2Tn,b be the maximal trees, which maximize the abovementioned indices. For this, we determine the structures of 1Tmax and 2Tmax from the following lemmas.Lemma 1.
Let2Tmax∈Tn,b with 1≤b<n−2/2 be a maximal tree. Then, it contains internal path of length one only.Proof.
Suppose, to the contrary, that2Tmax has an internal path of length greater than or equal to two. Let be an internal path of length greater than or equal to two in 2Tmax where u1 and uk be the branching vertices and ∀duj=2,1<j<k. Let a leaf w be adjacent to some vertex ui other than uj,1<j<k. Let T∗=2Tmax−uiw,u1u2,uk−1uk+u1uk,u2w,uk−1ui; then, T∗∈Tn,b and
(16)GO12Tmax−GO1T∗=4duk−du1−du1duk−8<0,since3≤duk<du1,GO22Tmax−GO2T∗=−du12duk+1−du1duk2+7+4duk2+6duk−34<0,since3≤duk<du1,HGO12Tmax−HGO1T∗=−du12duk2+11−du14duk2−2duk+32+29duk2+8duk−64<0,since3≤duk<du1,HGO22Tmax−HGO2T∗=−du14duk2−2duk+9−2du13duk3−duk2−duk+39−du12duk4+2duk3−6duk2+2duk+269−2du1duk4−duk3−duk2+duk+170+10duk4+28duk3+30duk2−924,<0,since3≤duk<du1,
a contradiction to2Tmax, due to the fact du1≥4 and duk≥3. Hence, 2Tmax contains internal path of length one only.Lemma 2.
Let2Tmax∈Tn,b with 1≤b<n−2/2 be a maximal tree. If 2Tmax contains ϱ1,i≠0,2<i≤4, then it contains pendent path of length at most two.Proof.
Suppose, to the contrary, that2Tmax has an pendent path of length greater than or equal to three. Let be a pendent path of length greater than or equal to three and a leaf w is connected to u in 2Tmax where u is a branching vertex. Then, we have another tree T∗=2Tmax−uw,u1u2,u2u3+u2w,u2u,u1u3 such that T∗∈Tn,b and
(17)GO12Tmax−GO1T∗=2−du<0,sincedu≥3,GO22Tmax−GO2T∗=10−3du−du2<0,sincedu≥3,HGO12Tmax−HGO1T∗=36−8du−5du2<0,sincedu≥3,HGO22Tmax−HGO2T∗=220−15du2−14du3−3du4<0,sincedu≥3,
a contradiction to2Tmax. Hence, 2Tmax contains a pendent path of length at most two.Lemma 3.
Let1Tmax∈Tn,b (respectively 2Tmax∈Tn,b) with 1≤b<n−2/2 be a maximal tree. If it contains ϱ2,i,i∈1,2,4, then it does not contain ϱ3,j,j∈1,3,4 and vice versa.Proof.
Suppose, to the contrary, that1Tmax (respectively 2Tmax) has ϱ2,i,ϱ3,i,i∈1,2,3,4. This means it contains vertices of degrees two and three simultaneously. Let a branching vertex u of degree three be adjacent to its neighbor vertices u1,u2 and u3=v with du1≥1 and du2≥1. Let v be a vertex of degree two which is adjacent to its neighbor vertices u and x. We obtained another tree T∗=2Tmax−uu1,uu2+vu1,vu1 such that T∗∈Tn,b and
(18)GO11Tmax−GO1T∗=−6−du1+du2<0,GO21Tmax−GO2T∗=−22−7du1+du2−du12+du12<0,HGO11Tmax−HGO1T∗=−106−16du1+du2−9du12+du22<0,HGO21Tmax−HGO2T∗=−1548−175du12+du22−74du13+du23−7du14+du24,<0,
a contradiction to the choice of1Tmax (respectively 2Tmax). Hence, 1Tmax (respectively 2Tmax) has no vertices of degrees two and three simultaneously.Lemma 4.
For any treeTmax∈Tn,b with 1≤b<n−2/2, the following result holds.
(19)DSTmax=4,4,⋯,4⏟b,2,2,⋯,2⏟n−3b−2,1,1,⋯,1⏟2b+2ifTmax∈1Tn,b,4,4,⋯,4⏟n−2b−2,3,3,⋯,3⏟3b−n+2,1,1,⋯,1⏟n−bifTmax∈2Tn,b.Proof.
LetTmax be a maximal tree in Tn,b. To find the number of vertices of different degrees of the abovementioned degree sequences, we have two cases:
Case: 1
IfV3=0, then V4=b are total branching vertices in Tmax. Since V2>0 and with the help of some already recorded results n=∑i=1ΔVi and 2n−1=∑i=1ΔiVi, we get V1=2b+2 and V2=n−V4−V1=n−3b−2.
Case: 2
IfV3>0, then V3+V4=b are the branching vertices in Tmax. Since V2=0, it is noted that there are n−b pendent vertices in Tmax. Again using the above results n=∑i=1ΔVi and 2n−1=∑i=1ΔiVi, we get V3=3b−n+2 and V4=n−2b−2.Lemma 5.
Let1Tmax∈Tn,b (respectively 2Tmax∈Tn,b) with 1≤b<n−2/2 be a maximal tree. It contains ϱ2,i,i∈1,2,4 iff 1≤b<n−2/3.Proof.
Let1Tmax be a maximal tree with 1≤b<n−2/3. Then, by Lemmas 3 and 4, 1Tmax has ϱ2,i,i∈1,2,4. So, it has at least one vertex of degree two. Also, by Lemma 3, there is no vertex of degree three in 1Tmax. So V2=n−3b−2≥1 which gives 3b≤n−3<n−2. Hence, b<n−2/3. Conversely, let 1≤b<n−2/3; this implies n≥3b+3>3b+2 and 1≤b. By using induction technique on b, we will show that there exists a vertex of degree two at least. For b=1, we have n>5 and it will be a starlike tree with a degree of branching vertex is four. Now assume that result is also true for b=k, and we have n≥3k+3 with k branching vertices where k≥1. Now we have to prove that it will be true for b=k+1. For this, let 1Tmax be a tree of order n≥3k+1+3 with k+1 number of branching vertices with a maximum degree of any branching vertex at most four. Let P:u0u1u2⋯ul−1ul be a longest path in 1Tmax with u1 be a branching vertex of degree at most four. We note that all neighbors of u1 be pendent vertices except u2. We obtained another tree T∗ after deleting all those pendent paths related to u1. It means T∗ has k+1−1=k branching vertices. So T∗ has order n≥3k+3. Hence, T∗ has at least one vertex of degree two. Thus, 1Tmax also has a degree two vertex at least. By induction, this completes the proof.Lemma 6.
Let2Tmax∈Tn,b with 1≤b<n−2/2 be a maximal tree. If it contains ϱ1,4≠0, then it has no ϱ3,3 in 2Tmax.Proof.
Suppose, to the contrary, that2Tmax has both ϱ3,3 and ϱ1,4. This means there are two vertices, say x,y, of degree three, and also, a leaf v is connected to a vertex w of degree four in 2Tmax. Assume that there is a unique path v−x that contains vertex y. Let xi,1≤i≤2 be the neighbors of vertex x different from y. If we obtained another tree T∗=2Tmax−xx1,xx2+vx1,vx2, then 2Tmax∈Tn,b and we have GO12Tmax−GO1T∗=−2<0,GO22Tmax−GO2T∗=−22<0,HGO12Tmax−HGO1T∗=−104<0, and HGO22Tmax−HGO2T∗=−3884<0, which is a contradiction to the choice of 2Tmax. Hence, if 2Tmax contains ϱ1,4≠0, then, it has no ϱ3,3 in 2Tmax.Lemma 7.
Let2Tmax∈Tn,b with 1≤b<n−2/2 be a maximal tree. Then, every vertex having degree three in 2Tmax is connected to one vertex at most, having degree four.Proof.
Suppose, to the contrary, that a vertexw of degree three is adjacent to its neighbors u and v of degree four each. By Lemma 3, there is no ϱ2,i in 2Tmax which means it has no vertex of degree two. Let a leaf x be connected to branching vertex v or u other than w. Then, a tree T∗ is obtained by deleting edges uw,vw,xv and adding edges uv,wx,vw; then, T∗∈Tn,b, and we get GO12Tmax−GO1T∗=−3<0,GO22Tmax−GO2T∗=−36<0,HGO12Tmax−HGO1T∗=−183<0, and HGO22Tmax−HGO2T∗=−9072<0, a contradiction to the choice of 2Tmax. Hence, we have the required result.Lemma 8.
Let2Tmax∈Tn,b with 1≤b<n−2/2 be a maximal tree. Then, it must contain vertex/vertices of degree four, and the induced graph from the vertex/vertices of degree four is a tree.Proof.
If1≤b<n−2/3, then by Lemma 5, we have at least one branching vertex, i.e., 1≤b, and by Lemma 3, 1Tmax (respectively 2Tmax) has no vertices of degrees two and three at a time. Also by Lemma 4, 1Tmax has no vertex of degree three so that the only branching vertices are the vertices of degree four, i.e., V4≥1. By Lemma 1, the induced graph from the vertex/vertices of degree four is a tree. Now if n−2/3≤b<n−2/2, then by Lemma 4, 2Tmax has no vertex of degree two and by Lemma 5, we have V4=n−2b−2. It follows V4≥1. Hence, by Lemma 1, we have the required result.Theorem 9.
LetTmax∈1Tn,b, where 1≤b<n−2/3; then, for 4,4,⋯,4⏟b,2,2,⋯,2⏟n−3b−2,1,1,⋯,1⏟2b+2,
(20)GO1Tmax≤8n+22b−181≤b<n−45,10n+12b−26n−45≤b<n−23,GO2Tmax≤16n+156b−841≤b<n−45,34n+66b−156n−45≤b<n−23,HGO1Tmax≤64n+698b−3901≤b<n−45,140n+318b−694n−45≤b<n−23,HGO2Tmax≤256n+19784b−127281≤b<n−45,1940n+11364b−19464n−45≤b<n−23.The equality holds iffTmax has degree sequence 4,4,⋯,4⏟b,2,2,⋯,2⏟n−3b−2,1,1,⋯,1⏟2b+2.Proof.
By Lemma8, we have ϱ4,4=V4−1=b−1. Now if 1≤b<n−2/3, then we have two cases:
Case 1. If 1≤b<n−4/5, then ϱ1,4=0. From (12)–(15), we get ϱ1,2=ϱ2,4=2b+2,ϱ2,2=n−5b−4. Then, (9) becomes
(21)TI^Tmax=ϱ1,2φ1,2+ϱ1,4φ1,4+ϱ2,2φ2,2+ϱ2,4φ2,4+ϱ4,4φ4,4,=2b+2φ1,2+n−5b−4φ2,2+2b+2φ2,4+b−1φ4,4,=2b+2φ1,2+φ2,4+n−5b−4φ2,2+b−1φ4,4.
It follows(22)GO1Tmax=24b−1+38b+1+8n−5b−4,=8n+22b−18,GO2Tmax=128b−1+108b+1+16n−5b−4,=16n+156b−84,HGO1Tmax=576b−1+442b+1+64n−5b−4,=64n+698b−390,HGO2Tmax=16384b−1+4680b+1+256n−5b−4,=256n+19784b−12728.
Case 2. For n−4/5≤b<n−2/3, if ϱ1,4≠0, then by Lemmas 1 and 2, we have ϱ2,2=0. From (12)–(15), we get ϱ1,2=ϱ2,4=n−3b−2,ϱ2,2=0,ϱ1,4=5b−n+4. Then, (9) becomes
(23)TI^Tmax=ϱ1,2φ1,2+ϱ1,4φ1,4+ϱ2,2φ2,2+ϱ2,4φ2,4+ϱ4,4φ4,4,=n−3b−2φ1,2+5b−n+4φ1,4+n−3b−2φ2,4+b−1φ4,4,=n−3b−2φ1,2+φ2,4+5b−n+4φ1,4+b−1φ4,4.
It follows(24)GO1Tmax=24b−1+95b−n+4+19n−3b−2,=10n+12b−26,GO2Tmax=128b−1+205b−n+4+54n−3b−2,=34n+66b−156,HGO1Tmax=576b−1+815b−n+4+221n−3b−2,=140n+318b−694,HGO2Tmax=16384b−1+4005b−n+4+2340n−3b−2,=1940n+11364b−19464,which completes the proof.In Figure1, for n=20, three trees T20,1, T20,2, and T20,3, having 1, 2, and 3 branching vertices, respectively, are in 1T20,b where 1≤b<n−4/5 and satisfies Theorem 9, Case 1. And next two trees T20,4 and T20,5, having 4 and 5 branching vertices, respectively, are in 1T20,b where n−4/5≤b<n−2/3 and satisfies Theorem 9, Case 2.Theorem 10.
LetTmax∈2Tn,b, where n−2/3≤b≤n−2/2; then, for 4,4,⋯,4⏟n−2b−2,3,3,⋯,3⏟3b−n+2,1,1,⋯,1⏟n−b,
(25)GO1Tmax≤18n−12b−42n−23≤b<3n−47,24n−26b−503n−47≤b<n−22,GO2Tmax≤80n−72b−248n−23≤b<3n−47,146n−226b−3363n−47≤b<n−22,HGO1Tmax≤360n−342b−1134n−23≤b<3n−47,672n−1070b−15503n−47≤b<n−22,HGO2Tmax≤10240n−13536b−36064n−23≤b<3n−47,21892n−40724b−516003n−47≤b<n−22.Figure 1
Five trees in the class of1T20,b where 1≤b<n−2/3.The equality holds iffTmax has degree sequence 4,4,⋯,4⏟n−2b−2,3,3,⋯,3⏟3b−n+2,1,1,⋯,1⏟n−b.Proof.
Again by Lemma8, we have ϱ4,4=V4−1=b−1. If n−2/3≤b<n−2/2, then we have two cases:
Case 1. For n−2/3≤b<3n−4/7, if ϱ1,4≠0, then by Lemma 6, ϱ3,3=0. From (12)–(15), we get ϱ1,3=6b−2n+4,ϱ1,4=3n−7b−4,ϱ3,4=3b−n+2. Then, (9) becomes
(26)TI^Tmax=ϱ1,3φ1,3+ϱ1,4φ1,4+ϱ3,3φ3,3+ϱ3,4φ3,4+ϱ4,4φ4,4,=6b−2n+4φ1,3+3n−7b−4φ1,4+3b−n+2φ3,4+n−2b−3φ4,4.
It follows(27)GO1Tmax=333b−n+2+24n−2b−3+93n−7b−4,=18n−12b−42,GO2Tmax=1083b−n+2+128n−2b−3+203n−7b−4,=80n−72b−248,HGO1Tmax=4593b−n+2+576n−2b−3+813n−7b−4,=360n−342b−1134,HGO2Tmax=73443b−n+2+16384n−2b−3+4003n−7b−4,=10240n−13536b−36064.
Case 2. For 3n−4/7≤b<n−2/2, if ϱ1,4=0, then by Lemma 6, ϱ3,3≠0. From (12)–(15), we get ϱ1,3=n−b,ϱ3,3=7b−3n+4,ϱ3,4=2n−4b−2. Then, (9) becomes
(28)TI^Tmax=ϱ1,3φ1,3+ϱ1,4φ1,4+ϱ3,3φ3,3+ϱ3,4φ3,4+ϱ4,4φ4,4,=n−bφ1,3+7b−3n+4φ3,3+2n−4b−2φ3,4+n−2b−3φ4,4.
It follows(29)GO1Tmax=157b−3n+4−382b−n+1+24n−2b−3+7n−b,=24n−26b−50,GO2Tmax=547b−3n+4−1682b−n+1+128n−2b−3+12n−b,=146n−226b−336,HGO1Tmax=2257b−3n+4−7222b−n+1+576n−2b−3+49n−b,=672n−1070b−1550,HGO2Tmax=29167b−3n+4−141122b−n+1+16384n−2b−3+144n−b,=21892n−40724b−51600,which completes the proof.In Figure2, for n=20, two trees T20,6 and T20,7, having 6 and 7 branching vertices, respectively, are in 2T20,b where n−2/3≤b<3n−4/7 and satisfies Theorem 10, Case 1. And next one tree T20,8, having 8 branching vertices, is in 2T20,b where 3n−4/7≤b<n−2/2 and satisfies Theorem 10, Case 2.Figure 2
Three trees in the class of2T20,b where n−2/3≤b<n−2/2.In Figure3, for n=20, one tree T20,9 having 9 branching vertices, is in T20,b where b=n−2/2 and this tree contains only vertices of degree one and three.Figure 3
One tree in the class ofT20,b where b=n−2/2.


## 3. Conclusions

Topological indices are the main tool for investigating the properties of different molecular descriptors by many researchers in the last decade. We have determined sharp upper bonds on the Gourava indices and hyper-Gourava indices with a fixed number of branching vertices for the classes ofn-vertex chemical trees 1Tn,b and 2Tn,b of Tn,b. The above-computed graph invariants are used as molecular descriptors in the construction of the theoretical models such as quantitative structure-activity relationships (QSARs) which relate the quantitative measure of a chemical structure to a biological property or a physical property and quantitative structure-property relationships (QSPRs) which relate mathematically physical/chemical properties to the structure of a molecule. The above results can be correlated with the physical properties like entropy, acentric factor, and standard enthalpy of vaporization, of hydrocarbons. We have given nine examples of the chemical graphs that can be verified by using the results of Theorems 9 and 10. At this stage, we left the lower bonds on the abovementioned indices for the collection of all chemical trees with n vertices and b branching vertices for the abovementioned classes as an open problem.



---

*Source: 3642849-2022-03-29.xml*