# Several Asymptotic Bounds on the Balaban Indices of Trees

Authors: Bo Deng; Chengfu Ye; Weilin Liang; Yalan Li; Xueli Su
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

The Balaban index (also called theJ index) of a connected graph G is a distance-based topological index, which has been successfully used in various QSAR and QSPR modeling. Although the index was introduced 30 years ago, there are few results on the asymptotic relations. In this paper, several asymptotic bounds on the Balaban indices of trees with diameters 3 and 4 are shown, respectively.


---

## Body

## 1. Introduction

All graphs considered in this paper are simple and undirected. LetG be a graph with its edge set EG and vertex set VG. We set VG=n and EG=m. The star of order n is denoted by Sn. The distance between vertices u and v in G is denoted by dGu,v, and the sum of the distance between vertex u and each vertex of G is denoted by σGu, that is, σGu=∑w∈VGdGu,w.The Balaban index [1] of a connected graph G (or the J index for short) is defined as(1)JG=mμ+1∑uv∈EG1σGuσGv,where μ is the cyclomatic number and μ=m−n+1.The Balaban index (also called theJ index) of a connected graph G is a distance-based topological index, which has been successfully used in various QSAR and QSPR modeling [2, 3]. Many applications in chemistry can be found in [4–6]. By comparing with the Wiener index regarding alkanes in [7], it was found that the Balaban index reduces the degeneracy of the latter index and provides much higher discriminating ability. So, the Balaban index is also called the sharpened Wiener index. Some results on the maximal and minimal Balaban index [8–10] have been presented. In [11–14], the asymptotic behaviors of the Balaban indices for various infinite families of graphs are observed.Until now, there are few results on the asymptotic relations on the Balaban index. In this paper, several asymptotic bounds on the Balaban indices of trees with diameters 3 and 4 are shown, respectively. The two kinds of trees are depicted as follows.If a tree is with diameter 3, then this tree can be obtained by attaching some pendent edges to the two end-vertices of one edge. Then, this tree is denoted byTn3,a,b, see Figure 1, which has n vertices, diameter 3, and satisfies that there are a pendent edges attached at one end-vertex of one edge and b pendent edges attached at the other end-vertex of the edge, where a≥1, b≥1, and a+b=n−2. The set of this kind of trees is denoted by Tn3,a,b.Figure 1
The graphTn3,a,b.The tree with ordern and diameter 4 denoted by Tnl4,a1,a2,…,al, see Figure 2, is obtained from a star Sl+1 by attaching a1,a2,…,al pendent edges to the l pendent vertices of the star, respectively, where ai≥0,1≤i≤l. The set of this kind of trees is denoted by Tnl4,a1,a2,…,al.Figure 2
The graphTnl4,a1,a2,…,al.


## 2. The Balaban Indices of Trees with Diameter 3

In this section, the asymptotic bounds on the Balaban indices of trees with diameter 3 will be given.Theorem 1.
For any treeTn3,a,b∈Tn3,a,b, we have(2)O2n15≤JTn3,a,b≤On2.Proof.
Supposea≤b. Then, by a+b=n−2, we have a≤n−2/2. By direct calculation, the Balaban index of Tn3,a,b=Tn3,a,n−a−2 is as follows:(3)JTn3,a,n−a−2=n−1⋅a3n−a−52n−a−3+12n−a−3n+a−1+n−a−22n+a−3n+a−1.
Through computation, the derivative ofJTn3,a,n−a−2 related to a is(4)∂JTn3,a,n−a−2∂a=n−12⋅a5n−2a−83n−a−52n−a−33/2+23n−a−52n−a−3+2+2a−n2n−a−3n+a−13/2−2n+a−12n+a−3+2+a−n3n+2a−42n+a−3n+a−13/2.
Next, the sign of∂JTn3,a,n−a−2/∂a will be determined. For the above equation, we see that the first two terms are positive, and the last three terms are nonpositive. Then, we use the sum of the first two terms to divide the sum of the absolute values of the last three terms. So, we get that(5)a5n−2a−8/3n−a−52n−a−33/2+2/3n−a−52n−a−3n−2a−2/2n−a−3n+a−13/2+2/n+a−12n+a−3+n−a−23n+2a−4/2n+a−3n+a−13/2=12n2−38n+a8−5n+303n−a−52n−a−33/2n−2a−2/n+a−12n−a−33/2+2/n+a−12n+a−3+n−a−23n+2a−4/2n+a−3n+a−13/2.
Denote the above fraction byfn,a. Observing this quotient, its value is equal to 1 if n=2k+2 and a=k for k=2,3,…,n−2/2. In this case, it means that Tn3,a,n−a−2 attains the minimum value. Otherwise, its value is less than 1 as n tends to infinity, that is,(6)limn⟶∞fn,a=473<1.
Thus, the derivative ofJTn3,a,n−a−2 related to a is negative as n is big enough. In this case, JTn3,a,n−a−2 increases along with parameter a decreasing. Since 1≤a≤⌊n−2/2⌋, we see that(7)JTn3,a,n−a−2≤JTn3,1,n−3,JTn3,a,n−a−2≥JTn3,n−2/2,n−2/2.
By calculation, we get(8)JTn3,1,n−3=On2,JTn3,n−2/2,n−2/2=O2n15.
Hence, we obtain(9)O2n15≤JTn3,a,b≤On2.


## 3. The Balaban Indices of Trees with Diameter 4

In this section, we present some asymptotic bounds for the Balaban indices of trees with diameter 4.Theorem 2.
For any treeTnl4,a1,a2,…,al∈Tnl4,a1,a2,…,al, we have(10)J4,a1,a2,…,al≤On2.Proof.
The Balaban index of a treeTnl4,a1,a2,…,al is as follows:(11)JTnl4,a1,a2,…,al=n−1∑i=1lai4n−2ai−l−63n−2ai−l−4+∑i=1l12n−l−23n−2ai−l−4.
Suppose1≤a1≤a2, and let a1=a and c=n−a−a2. Then,(12)JTnl4,a1,a2,…,al=n−1⋅a4n−2a−l−63n−2a−l−4+n−a−c2n+2a+2c−l−6n+2a+2c−l−4+∑i=3lai4n−2ai−l−63n−2ai−l−4+12n−l−23n−2a−l−4+12n−l−2n+2a+2c−l−4+∑i=3l12n−l−23n−2ai−l−4.
And we get the derivative ofJTnl4,a,a2,…,al related to a as follows:(13)∂JTnl4,a,a2,⋯,al∂a=n−1⋅−2−l+2n−2−l+2n−4−2a−l+3n3/2+1−4−2a−l+3n−6−2a−l+4n1/2−−2−l+2n−2−l+2n−4−l+n+2a+2c3/2−1−4−l+n+2a+2c−6−l+2n+2a+2c1/2+a−20−8a−4l+14n2−4−2a−l+3n−6−2a−l+4n3/2−−a−c+n−20−4l+6n+8a+8c2−4−l+n+2a+2c−6−l+2n+2a+2c3/2.
The sum of positive terms above is denoted byS+n,a,l, i.e.,(14)S+n,a,l=n−1⋅−2−l+2n−2−l+2n−4−2a−l+3n3/2+1−4−2a−l+3n−6−2a−l+4n1/2+a−20−8a−4l+14n2−4−2a−l+3n−6−2a−l+4n3/2.
And the sum of absolute values of negative terms above is denoted byS−n,a,l, i.e.,(15)S−n,a,l=n−1⋅−2−l+2n−2−l+2n−4−l+n+2a+2c3/2+1−4−l+n+2a+2c−6−l+2n+2a+2c1/2+−a−c+n−20−4l+6n+8a+8c2−4−l+n+2a+2c−6−l+2n+2a+2c3/2.
Then, we useS+n,a,l to divide S−n,a,l, and we get(16)limn⟶∞S−n,a,lS+n,a,l=523/2>1.
So, the derivative ofJTnl4,a1,a2,…,al related to a1 is less than 0 as n is big enough. It means that the corresponding Balaban index increases along with the number of pendent edges a1 decreasing and the number of pendent edges a2 increasing, i.e.,(17)JTnl4,a1,a2,…,al≤JTnl4,a1−1,a2+1,…,al.
Analogously, we obtain(18)JTnl4,a1,a2,…,al≤JTnl4,1,a1+a2+a3+⋯al−1,0,…,0=JTnl4,1,n−l−2,0,…,0.
For the above treeTnl4,1,n−l−2,0,…,0, it can be seen that there are only two numbers, i.e., 1 and n−l−2, as the numbers of pendent edges, respectively, attach to two pendent vertices of a star Sl+1. Thus, it is easy to check that(19)JTnl4,1,n−l−2,0,…,0=On2.
Hence,(20)JTnl4,a1,a2,…,al≤On2.
On the contrary, the asymptotically tight lower bound of such a tree is not easy to be given due to the determination of parameterl, but we find that, in Tnl4,a1,a2,…,al, the tree attained the asymptotically tight lower bound which possesses a property satisfying ai−aj≤1 for 1≤i≠j≤l. In case of l=2, we obtain the following result.Theorem 3.
For any treeTn24,a1,a2∈Tn24,a1,a2, where 1≤a1≤a2, we have(21)JTn24,a1,a2≥On6.Proof.
From the proof of Theorem2, we see that the derivative of JTn24,a1,a2 related to a1 is less than 0 as n is big enough. Thus, if a1=⌊n−3/2⌋,a2=⌈n−3/2⌉, then(22)JTn24,a1,a2≥JTn24,n−32,n−32.
Note that(23)JTn24,n−32,n−32=On6.
Thus,(24)JTn24,a1,a2≥On6.



---

*Source: 2081241-2020-11-06.xml*