Convexity result and trees with large Balaban index

Let T be a tree with n ≥ 4 vertices. If T is not a star, then J(T) ≤ J(D_n-2,2) with equality if and only if J(T) = J(D_n-2,2).

To prove the above mentioned results, the authors used so called edge-lifting and path-sliding transformations, which both increase Balaban index.

Let G₁and G₂be two graphs with n₁and n₂vertices, respectively, n₁,n₂≥ 2. If G is the graph obtained from G₁and G₂by adding an edge between a vertex u^* of G₁and a vertex v^* of G₂, G^' is the graph obtained by identifying u^* of G₁to v^* of G₂and adding a pendant edge to u^*(v^*), then G^' is called the edge-lifting transformation of G and we have J(G) < J(G^').

Let G₀be a graph with n₀≥ 2 vertices, and P = v₁v₂· · ·v_r a path of length r -1 ≥ 2. If G (resp. G^') is the graph obtained by identifying a vertex v^* of G₀to v_k-1(resp. v_k) in P, 2≤k≤[r−12]$2\le k\le \left[ \frac{r-1}{2} \right]$then G^' is called the path-sliding transformation of G and we have J(G) < J(G^').

J (D_n-x,x), as a function of x, is convex.

It should be noted that in the proof of Deng the function J (D_n-x,x) is defined in such a way that it is a continuous function, and the second derivative is used to show that it is convex. In what follows we will show that Theorem 4 can be generalized. For that we need the notion of a discrete convex function. This concept can be introduced in several different ways (an interested reader should consult [24]), but generally a (discrete) function f is strictly convex if for every x₀< x₁< x₂ from the domain of f it holds

f(x1)<x2−x1x2−x0f(x0)+x1−x0x2−x0f(x2).$$f\left( {{x}_{1}} \right)<\frac{{{x}_{2}}-{{x}_{1}}}{{{x}_{2}}-{{x}_{0}}}f\left( {{x}_{0}} \right)+\frac{{{x}_{1}}-{{x}_{0}}}{{{x}_{2}}-{{x}_{0}}}f\left( {{x}_{2}} \right).$$

However, if the domain is the set of integers greater than or equal to b, then the above property is equivalent to

2f(x0+1)<f(x0)+f(x0+2)$$2f\left( {{x}_{0}}+1 \right)<f\left( {{x}_{0}} \right)+f\left( {{x}_{0}}+2 \right)$$

for all x₀≥ b.

Let G be a graph with two distinct vertices u^* and v^*. Let a ≥ 2 and 0 ≤ x ≤ a. Attach x pendant edges to u^*, attach a -x pendant edges to v^*, and denote the resulting graph by G_x. Then J(G_x), as a (discrete) function of x, is strictly convex.

Proof. As mentioned above, it suffices to prove that J (G_x)+J(G_x+2) > 2J(G_x+1) for every x, 0 ≤ x ≤ a -2.

Therefore, it is sufficient to restrict ourselves to the case a = 2 and to prove J (G₀)+J(G₂) > 2J(G₁).

Further, since all the graphs G_x, 0 ≤ x ≤ 2, have the same number of vertices and edges, it suffices to prove the strict convexity of ∑uv∈E(Gx)1wGx(u)⋅wGx(v).$\sum\nolimits_{uv\in E\left( {{G}_{x}} \right)}{\frac{1}{\sqrt{{{w}_{{{G}_{x}}}}\left( u \right)\cdot {{w}_{{{G}_{x}}}}\left( v \right)}}}\,.$We divide the proof into two claims.

Let uv ϵ E (G). Then1wGx(u)⋅wGx(v),$\frac{1}{\sqrt{{{w}_{{{G}_{x}}}}\left( u \right)\cdot {{w}_{{{G}_{x}}}}\left( v \right)}}\,,$as a function of x, is strictly convex.

Denote c = w_G1(u) and d = w_G1(v). Further, denote γ = w_G1(u)-w_G0(u) and δ = w_G1(v)-w_G0(v). Then w_G0(u) = c -γ and w_G0(v) = d -δ. Since γ (δ, respectively) is the difference corresponding to removing a pendant edge from v^* and adding it to u^*, we have w_G2(u) = c +γ and w_G2(v) = d +δ. Hence, we need to prove

1wG0(u)⋅wG0(v)+1wG2(u)⋅wG2(v)>2wG1(u)⋅wG1(v),$$\frac{1}{\sqrt{{{w}_{{{G}_{0}}}}\left( u \right)\cdot {{w}_{{{G}_{0}}}}\left( v \right)}}+\frac{1}{\sqrt{{{w}_{{{G}_{2}}}}\left( u \right)\cdot {{w}_{{{G}_{2}}}}\left( v \right)}}>\frac{2}{\sqrt{{{w}_{{{G}_{1}}}}\left( u \right)\cdot {{w}_{{{G}_{1}}}}\left( v \right)}}\,,$$

which is equivalent to

(1)1(c−γ)(d−δ)+1(c+γ)(d+δ)>2cd.$$\frac{1}{\sqrt{\left( c-\gamma \right)\left( d-\delta \right)}}+\frac{1}{\sqrt{\left( c+\gamma \right)\left( d+\delta \right)}}>\frac{2}{\sqrt{cd}}.$$

Observe that c,d > 0, but γ and δ can be negative. Anyway, since c - γ = w_G0(u) > 0 and c+γ = w_G2(u) > 0, we have c - |γ| > 0. Analogously d -|δ| > 0, and so

(2)c2d2>(c2−γ2)(d2−δ2)cd>(c+γ)(c−γ)(d+δ)(d−δ)2(c+γ)(c−γ)(d+δ)(d−δ)⋅cd>(c+γ)(c−γ)(d+δ)(d−δ).$$\begin{array}{*{35}{r}}\sqrt{{{c}^{2}}{{d}^{2}}}>\sqrt{\left( {{c}^{2}}-{{\gamma }^{2}} \right)\left( {{d}^{2}}-{{\delta }^{2}} \right)}\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \\cd>\sqrt{\left( c+\gamma \right)\left( c-\gamma \right)\left( d+\delta \right)\left( d-\delta \right)} \\2\sqrt{\left( c+\gamma \right)\left( c-\gamma \right)\left( d+\delta \right)\left( d-\delta \right)}\cdot cd>\left( c+\gamma \right)\left( c-\gamma \right)\left( d+\delta \right)\left( d-\delta \right).\,\,\, \\\end{array}$$

Now suppose that |cδ| ≥ |dγ|. (The case |dγ| ≥ |cδ| can be proved analogously since the resulting formula is symmetric, see below.) Then, regardless if cδ is positive or negative, we have

cδ(cδ+dγ)>0.$c\delta \left( c\delta +d\gamma \right)>0.$

Since d²-δ²> 0, see above, we have

(3)(d2−δ2)γ2+cδ(cδ+dγ)>0d2γ2−δ2γ2+c2δ2+cdγδ>02c2d2+2cdγδ>2c2d2−2c2δ2−2d2γ2+2γ2δ2(c+γ)(d+δ)+(c−γ)(d−δ)cd>2(c+γ)(d+δ)(c−γ)(d−δ).$$\begin{array}{*{35}{l}}\,\,\,\,\,\,\,\,\,\,\,\,\,\left( {{d}^{2}}-{{\delta }^{2}} \right){{\gamma }^{2}}+c\delta \left( c\delta +d\gamma \right)>0 \\\,\,\,\,\,\,\,\,\,\,\,\,\,\,{{d}^{2}}{{\gamma }^{2}}-{{\delta }^{2}}{{\gamma }^{2}}+{{c}^{2}}{{\delta }^{2}}+cd\gamma \delta >0 \\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,2{{c}^{2}}{{d}^{2}}+2cd\gamma \delta >2{{c}^{2}}{{d}^{2}}-2{{c}^{2}}{{\delta }^{2}}-2{{d}^{2}}{{\gamma }^{2}}+2{{\gamma }^{2}}{{\delta }^{2}} \\\left( c+\gamma \right)\left( d+\delta \right)+\left( c-\gamma \right)\left( d-\delta \right)cd>2\left( c+\gamma \right)\left( d+\delta \right)\left( c-\gamma \right)\left( d-\delta \right). \\\end{array}$$

Summing (2) and (3) gives

((c+γ)(d+δ)cd+(c−γ)(d−δ)cd)2>(2(c+γ)(d+δ)(c−γ)(d−δ))2,$${{\left( \sqrt{\left( c+\gamma \right)\left( d+\delta \right)}\sqrt{cd}+\sqrt{\left( c-\gamma \right)\left( d-\delta \right)}\sqrt{cd} \right)}^{2}}>{{\left( 2\sqrt{\left( c+\gamma \right)\left( d+\delta \right)}\sqrt{\left( c-\gamma \right)\left( d-\delta \right)} \right)}^{2}}\,,$$

which is equivalent to (1). This establishes the claim.

Function∑uv∈E(Gx)\E(G)1wGx(u)⋅wGx(v)$\sum\limits_{uv\in E\left( {{G}_{x}} \right)\backslash E\left( G \right)}{\frac{1}{\sqrt{{{w}_{{{G}_{x}}}}\left( u \right)\cdot {{w}_{{{G}_{x}}}}\left( v \right)}}}$is strictly convex.

Let d_G(u^*,v^*) = l. Denote c = w_G(u^*) and d = w_G(v^*). Then w_G1(u^*) = c+1+l +1, w_G2(u^*) = c+2, w_G0(v^*) = d +2 and w_G1(v^*) = d +l+2. Further, denote by u^' a pendant vertex attached to u^* and denote by v^' a pendant vertex attached to v^*. If |V(G)|=t, then w_G1(u^')=c+l+t+2, w_G2(u^')=c+t+2, w_G0(v^')=d+t+2 and w_G1(v^') = d+l+t +2. Denote g(x)=∑uv∈E(Gx)\E(G)1wGx(u)⋅wGx(v).$g\left( x \right)=\sum\limits_{uv\in E\left( {{G}_{x}} \right)\backslash E\left( G \right)}{\frac{1}{\sqrt{{{w}_{{{G}_{x}}}}\left( u \right)\cdot {{w}_{{{G}_{x}}}}\left( v \right)}}}\,.$Then

g(0)=2(d+2)(d+t+2),$$g\left( 0 \right)=\frac{2}{\sqrt{\left( d+2 \right)\left( d+t+2 \right)}}\,,$$

g(1)=1(c+l+2)(c+l+t+2)+1(d+l+2)(d+l+t+2),g(2)=2(c+2)(c+t+2).$$\begin{array}{*{35}{l}}g\left( 1 \right)=\frac{1}{\sqrt{\left( c+l+2 \right)\left( c+l+t+2 \right)}}+\frac{1}{\sqrt{\left( d+l+2 \right)\left( d+l+t+2 \right)}}, \\g\left( 2 \right)=\frac{2}{\sqrt{\left( c+2 \right)\left( c+t+2 \right)}}\,. \\\end{array}$$

Since l ≥ 1, we have

2(d+2)(d+t+2)>2(d+l+2)(d+l+t+2)2(c+2)(c+t+2)>2(c+l+2)(c+l+t+2)$$\begin{array}{*{35}{l}}\frac{2}{\sqrt{\left( d+2 \right)\left( d+t+2 \right)}}>\frac{2}{\sqrt{\left( d+l+2 \right)\left( d+l+t+2 \right)}} \\\,\frac{2}{\sqrt{\left( c+2 \right)\left( c+t+2 \right)}}>\frac{2}{\sqrt{\left( c+l+2 \right)\left( c+l+t+2 \right)}} \\\end{array}$$

and summing the two inequalities above gives g(0)+g(2) > 2g(1) as required. This establishes the claim.

Claims 1 and 2 assure that ∑uv∈E(Gx)1wGx(u)⋅wGx(v)$\sum\nolimits_{uv\in E\left( {{G}_{x}} \right)}{\frac{1}{\sqrt{{{w}_{{{G}_{x}}}}\left( u \right)\cdot {{w}_{{{G}_{x}}}}\left( v \right)}}}$is a strictly convex function, since the sum of strictly convex functions is a strictly convex function. Thus the claim of the theorem follows.

We remark that the fact that S_n and D_n-2,2 are trees of order n with the largest and second largest, respectively, Balaban index is a direct consequence of Theorem 5.

Let ν be an invariant on the class of trees. We say that ν is star-convex, if for every tree G with two specific vertices u^* and v^* and for every a ≥ 2, the invariant ν is strictly convex on G_x, which is obtained from G by attaching x pendant edges to u^* and a -x pendant edges to v^*. Further, if n(T^') > ν(T) when T^' is obtained from T by path-sliding or edge-lifting, and moreover ν is star-convex, then we say that ν has SLC-property (which is a short notation for sliding-lifting-convexity property). By Theorems 2, 3 and 5, Balaban index has the SLC-property. We remark that also the sum-Balaban index has the SLC-property, see [22].

For t ≥ 2 we have

J(Dn−t,t)=(n−1)(n−t−1(2n+t−4)(n+t−2)+1(n+t−2)(2n−t−2)+1(2n−t−2)(3n−t−4)).$$\begin{align}& J\left( {{D}_{n-t,t}} \right)=\left( n-1 \right)\left( \frac{n-t-1}{\sqrt{\left( 2n+t-4 \right)\left( n+t-2 \right)}}+\frac{1}{\sqrt{\left( n+t-2 \right)\left( 2n-t-2 \right)}} \right. \\ & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\left. +\frac{1}{\sqrt{\left( 2n-t-2 \right)\left( 3n-t-4 \right)}} \right)\,. \\ \end{align}$$

A caterpillar H_a1,_a2,…,_ad-₁ is a tree consisting of a diametric path of length d (i.e., with d +1 vertices) and a couple of pendant edges, such that the degrees of vertices of the diametric path are 1,a₁,a₂, · · · ,a_d-1, 1. Due to symmetry, we may assume that a₁≥ a_d-1 in H_a1,_a2,⋯,_ad-₁ . See Figure 2 for an example.

Fig. 2

First we find T₃. Notice that there is only one tree on 3 vertices and only two trees on 4 vertices. Thus only the cases when n ≥ 5 are considered when searching for T₃.

Let ν be an invariant with SLC-property. If{T1v,T2v}={Sn,Dn−2,2}$\left\{ T_{1}^{v},T_{2}^{v} \right\}=\left\{ {{S}_{n}},{{D}_{n-2,2}} \right\}$, thenT3v∈{Dn−3,3,H2,n−3,2}.$T_{3}^{v}\in \left\{ {{D}_{n-3,3,}}{{H}_{2,n-3,2}} \right\}.$

Proof. Since edge-lifting reduces the diameter at most by 1, it suffices to consider trees with diameters 3 and 4. Since ν is star-convex, the only candidate among trees of diameter 3 is D_n-3,₃.

As regards trees of diameter 4, due to edge-lifting it suffices to consider those whose vertices of degrees at least 2 form a path, i.e., the caterpillars. Hence, we have to consider caterpillars H_a,_b,_c. Observe that all a, b and c are at least 2. However, if at least two from a, b and c are at least 3, then ν(H_a,_b,_c) < n(D_n-3,₃) due to edge-lifting. Moreover, ν(H_n-3,_2,2) < n(H₂,_n-3,₂) due to path-sliding if n ≥ 6, while if n = 5 then H₂,_n-3,₂ = H_n-3,₂,₂. Therefore, T3v∈{Dn−3,3,H2,n−3,2}.$T_{3}^{v}\in \left\{ {{D}_{n-3,3,}}{{H}_{2,n-3,2}} \right\}.$

Now we can state the result for T₃.

The following holds:

T3={P5,ifn=5Dn−3,3,ifn≥6.$${{T}_{3}}=\left\{ \begin{array}{*{35}{l}}{{P}_{5}},\,\,\,\,\,\,\,\,\,\,ifn=5 \\{{D}_{n-3,3,}}\,\,ifn\ge 6. \\\end{array} \right.$$

Proof. Since {T_i; 1 ≤ i ≤ 2} = {S_n,D_n-2,₂} and the Balaban index has SLC-property, it suffices to compare J (D_n-3,₃) and J (H₂,_n-3,₂), by Lemma 7. Since for n = 5 the graph D_n-3,₃ with n -3 ≥ 3 does not exist (observe that D_n-3,₃ should be D₃,₂, which is T₂ in this case), we have T₃ = H₂,₂,₂ = P₅. In what follows we assume n ≥ 6.

By Lemma 6 we have

J(Dn−3,3)=(n−1)(2(3n−7)(2n−5)+1(2n−5)(n+1)+n−4(n+1)(2n−1)).$$J\left( {{D}_{n-3,3}} \right)=\left( n-1 \right)\left( \frac{2}{\sqrt{\left( 3n-7 \right)\left( 2n-5 \right)}}+\frac{1}{\sqrt{\left( 2n-5 \right)\left( n+1 \right)}}+\frac{n-4}{\sqrt{\left( n+1 \right)\left( 2n-1 \right)}} \right)\,.$$

In H₂,_n-3,₂ there are also four orbits of vertices with value of w equal to 3n-5, 2n-3, n +1 and 2n-1.

Therefore

J(H2,n−3,2)=(n−1)(2(3n−5)(2n−3)+2(2n−3)(n+1)+n−5(n+1)(2n−1)).$$J\left( {{H}_{2,n-3,2}} \right)=\left( n-1 \right)\left( \frac{2}{\sqrt{\left( 3n-5 \right)\left( 2n-3 \right)}}+\frac{2}{\sqrt{\left( 2n-3 \right)\left( n+1 \right)}}+\frac{n-5}{\sqrt{\left( n+1 \right)\left( 2n-1 \right)}} \right)\,.$$

Since f(x)=1x$f\left( x \right)=\frac{1}{\sqrt{x}}$is a convex function, we have 12n−5+12n−1>22n−3,$\frac{1}{\sqrt{2n-5}}+\frac{1}{\sqrt{2n-1}}>\frac{2}{\sqrt{2n-3}},$and so

1(2n−5)(n+1)+1(2n−1)(n+1)>2(2n−3)(n+1).$$\frac{1}{\sqrt{\left( 2n-5 \right)\left( n+1 \right)}}+\frac{1}{\sqrt{\left( 2n-1 \right)\left( n+1 \right)}}>\frac{2}{\sqrt{\left( 2n-3 \right)\left( n+1 \right)}}.$$

Since 2(3n−7)(2n−5)>2(3n−5)(2n−3),$\frac{2}{\sqrt{\left( 3n-7 \right)\left( 2n-5 \right)}}>\frac{2}{\sqrt{\left( 3n-5 \right)\left( 2n-3 \right)}}\,,$we get J(D_n-3,₃) > J(H₂,_n-3,₂). Thus for n ≥ 6, D_n-3,₃ is a tree with the third maximum value of Balaban index.

In the sequel, we will refer to the following two facts from calculus.

Let a, b, c, d, and e, be constants such that b,d > 0. Then,

(4)limn→∞n+a(bn+c)(dn+e)=1bd.$$\underset{n\to \infty }{\mathop{\lim }}\,\frac{n+a}{\sqrt{\left( bn+c \right)\left( dn+e \right)}}=\frac{1}{\sqrt{bd}}.$$

Let a, b, c, d, e, and f be constants. Then,

(5)limn→∞(n+a)(n+b(n+c)(2n+d)−n+b(n+e)(2n+f))=2(e−c)+(f−d)42.$$\underset{n\to \infty }{\mathop{\lim }}\,\left( n+a \right)\left( \frac{n+b}{\sqrt{\left( n+c \right)\left( 2n+d \right)}}-\frac{n+b}{\sqrt{\left( n+e \right)\left( 2n+f \right)}} \right)=\frac{2\left( e-c \right)+\left( f-d \right)}{4\sqrt{2}}.$$

Proof. Starting from the left side, we derive

limn−∞(n+a)(n+b(n+c)(2n+d)−n+b(n+e)(2n+f))=limn→∞(n+a)(n+b)(n+c)(2n+d)(n+e)(2n+f)⋅limn→∞((n+e)(2n+f)−(n+c)(2n+d))=12limn→∞(n+e)(2n+f)−(n+c)(2n+d)(n+e)(2n+f)+(n+c)(2n+d)=2(e−c)+(f−d)42.$$\begin{array}{*{35}{l}}\underset{n-\infty }{\mathop{\lim }}\,\left( n+a \right)\left( \frac{n+b}{\sqrt{\left( n+c \right)\left( 2n+d \right)}}-\frac{n+b}{\sqrt{\left( n+e \right)\left( 2n+f \right)}} \right) \\=\underset{n\to \infty }{\mathop{\lim }}\,\frac{\left( n+a \right)\left( n+b \right)}{\sqrt{\left( n+c \right)\left( 2n+d \right)\left( n+e \right)\left( 2n+f \right)}}\cdot \underset{n\to \infty }{\mathop{\lim }}\,\left( \sqrt{\left( n+e \right)\left( 2n+f \right)}-\sqrt{\left( n+c \right)\left( 2n+d \right)} \right) \\=\frac{1}{2}\underset{n\to \infty }{\mathop{\lim }}\,\frac{\left( n+e \right)\left( 2n+f \right)-\left( n+c \right)\left( 2n+d \right)}{\sqrt{\left( n+e \right)\left( 2n+f \right)}+\sqrt{\left( n+c \right)\left( 2n+d \right)}} \\=\frac{2\left( e-c \right)+\left( f-d \right)}{4\sqrt{2}}\,. \\\end{array}$$

When searching for T₄,T₅ and T₆, we assume that n is at least 6, since otherwise there are less than 4 non-isomorphic trees and T₄ does not exist.

Let ν be an invariant with SLC-property. If{T1v,T2v,T3v}={Sn,Dn−2,2,Dn−3,3},thenT4v∈$\left\{ T_{1}^{v},T_{2}^{v},T_{3}^{v} \right\}=\left\{ {{S}_{n}},{{D}_{n-2,2}},{{D}_{n-3,3}} \right\},\,\,then\,\,T_{4}^{v}\in ${Dn−4,4,H2,n−3,2}.$\left\{ {{D}_{n-4,4}},{{H}_{2,n-3,2}} \right\}\,.$

Proof. Analogously as in Lemma 7, when looking for T4v$T_{4}^{v}$one has to consider D_n-4,₄ and caterpillars H_a,_b,_c. However, if at least two from a,b,c are at least 4, then ν(H_a,_b,_c) < ν(D_n-4,₄) due to edge-lifting. Similarly, if a ≥ 4 and one of b,c is at least 3, then ν(H_a,_b,_c) < n(D_n-4,₄) due to edge-lifting. Therefore it suffices to consider D_n-4,₄, H₂,_n-3,₂, H₃,_n-4,₂, H₃,_n-5,₃ and H_n-3,₂,₂. However, ν(H_n-3,₂,₂) < ν(H₂,_n-3,₂) due to path-sliding. Further, ν(D₄,_n-4)+ν(H₃,_n-4,₂) > 2ν(H₃,_n-4,₂) due to star-convexity, and so n(D_n-4,₄) > ν(H₃,_n-4,₂). Finally, 2n(H₄,_n-5,₂) > 2n(H₃,_n-5,₃) due to star-convexity and ν(D_n-4,₄) > ν(H₄,_n-5,₃) due to edge-lifting, which means that ν(D_n-4,₄) > ν(H₃,_n-5,₃). Therefore, T4v$T_{4}^{v}$2 {D_n-4,₄,H₂,_n-3,₂}.

The following holds:

T4={D4,4,ifn=8H2,n−3,2,ifn≥6,n≠8.$${{T}_{4}}=\left\{ \begin{array}{*{35}{l}}{{D}_{4,4}}, & if\,n=8 \\{{H}_{2,n-3,2}}, & if\,n\ge 6,\,n\ne 8\,. \\\end{array} \right.$$

Proof. Since for n ≥ 6 we have {T_i; 1 ≤ i ≤ 3} = {S_n,D_n-2,₂,D_n-3,₃} and the Balaban index has SLC-property, it suffices to compare J(H₂,_n-3,₂) and J(D_n-4,₄), by Lemma 11. As described in the proof of Proposition 8,

J(H2,n−3,2)=(n−1)(2(3n−5)(2n−3)+2(2n−3)(n+1)+n−5(n+1)(2n−1)),$$J\left( {{H}_{2,n-3,2}} \right)=\left( n-1 \right)\left( \frac{2}{\sqrt{\left( 3n-5 \right)\left( 2n-3 \right)}}+\frac{2}{\sqrt{\left( 2n-3 \right)\left( n+1 \right)}}+\frac{n-5}{\sqrt{\left( n+1 \right)\left( 2n-1 \right)}} \right)\,,$$

and by Lemma 6,

J(Dn−4,4)=(n−1)(3(3n−8)(2n−6)+1(2n−6)(n+2)+n−5(n+2)2n).$$J\left( {{D}_{n-4,4}} \right)=\left( n-1 \right)\left( \frac{3}{\sqrt{\left( 3n-8 \right)\left( 2n-6 \right)}}+\frac{1}{\sqrt{\left( 2n-6 \right)\left( n+2 \right)}}+\frac{n-5}{\sqrt{\left( n+2 \right)2n}} \right)\,.$$

Since there is no D_n-4,₄ for n ≤ 7, we have T₄ = H₂,_n-3,₂ if 6 ≤ n ≤ 7. For n ≥ 9, the following holds:

(6)J(H2,n−3,2)>J(Dn−4,4),$$J\left( {{H}_{2,n-3,2}} \right)>J\left( {{D}_{n-4,4}} \right)\,,$$

which implies that T₄ = H₂,_n-3,₂, for n ≥ 9. Note that showing (6) analytically would be extremely long and tedious and we would like to omit such a proof here. In order to convince the reader we show that the difference J (H₂,_n-3,₂)-J(D_n-4,₄) tends to a positive constant. By (4) and (5) we have

limn→∞(J(H2,n−3,2)−J(Dn−4,4))=26+22−36−12+342=73−446=·0.8291885.$$\underset{n\to \infty }{\mathop{\lim }}\,\left( J\left( {{H}_{2,n-3,2}} \right)-J\left( {{D}_{n-4,4}} \right) \right)=\frac{2}{\sqrt{6}}+\frac{2}{\sqrt{2}}-\frac{3}{\sqrt{6}}-\frac{1}{\sqrt{2}}+\frac{3}{4\sqrt{2}}=\frac{7\sqrt{3}-4}{4\sqrt{6}}\overset{\centerdot }{\mathop{=}}\,0.8291885.$$

Let us remark that the difference J (H₂,_n-3,₂)-J(D_n-4,₄) is increasing with n, and we obtain the first four decimals 0:8291 of the above limit when n is of order 8 · 104.

Finally, (6) does not hold for n = 8, so for this order T₄ = D₄,₄.

Let n ≥ 7. Then by R_n we denote the graph obtained from a star on n -3 vertices by subdividing three distinct edges, see Figure 3 for R₁₁. Now we determine T₅.

Fig. 3

Let ν be an invariant with SLC-property. If{Tiv;1≤i≤4}={Sn,Dn−2,2,Dn−3,3,H2,n−3,2},$\left\{ T_{i}^{v};1\le i\le 4 \right\}=\left\{ {{S}_{n}},{{D}_{n-2,2}},{{D}_{n-3,3}},{{H}_{2,n-3,2}} \right\}\,,$thenT5v∈{Dn−4,4,Hn−3,2,2}.$T_{5}^{v}\in \left\{ {{D}_{n-4,4}},{{H}_{n-3,2,2}} \right\}.$

Proof. Notice that T5v$T_{5}^{v}$must be of diameter 3, 4 or 5, since H₂,_n-3,₂ has diameter 4. So, first consider trees of diameter 5. If T5v$T_{5}^{v}$has diameter 5, it must have the property that every edge-lifting of T5v$T_{5}^{v}$results in H₂,_n-3,₂.Consequently, T5v$T_{5}^{v}$has a unique vertex of degree at least 3 and even in this case one can choose edge-lifting resulting in a tree of diameter 4 other than H₂,_n-3,₂. Hence, it suffices to consider D_n-4,₄ and trees of diameter 4.

If T5v$T_{5}^{v}$has diameter 4 and is a caterpillar, then analogously as in Lemma 11 the candidates are H₃,_n-4,₂, H₃,_n-5,₃ and H_n-3,₂,₂. However, in Lemma 11 we have shown that ν(D_n-4,₄) > ν(H₃,_n-4,₂) and ν(D_n-4,₄) > ν(H₃,_n-5,₃). If T5v$T_{5}^{v}$has diameter 4 and is not a caterpillar, then the central vertex of a diametric path of T5v$T_{5}^{v}$is adjacent with three distinct vertices of degree at least 2, and every edge-lifting of T5v$T_{5}^{v}$must result in H₂,_n-3,₂. So T5v$T_{5}^{v}$is R_n. We have ν(H₃,_n-4,₂)+ν(H₃,_n-4,₂) > 2ν(R_n) by star-convexity. Since ν(D_n-4,₄) > ν(H₃,_n-4,₂), we have ν(D_n-4,₄) > ν(R_n). Therefore, T5v$T_{5}^{v}$ϵ {D_n-4,₄,H_n-3,₂,₂}.

The following holds:

T5={H2,5,2,ifn=8Hn−4,4,if9≤n≤17Hn−3,2,2,ifn∈{6,7}orn≥18.$${{T}_{5}}=\left\{ \begin{array}{*{35}{l}}{{H}_{2,5,2}},\,\,\,\,\,\,\,\,if\,n=8 \\{{H}_{n-4,4}},\,\,\,\,\,\,\,if\,9\le n\le 17 \\{{H}_{n-3,2,2}},\,\,\,\,if\,n\in \left\{ 6,7 \right\}\,\,or\,n\ge 18\,. \\\end{array} \right.$$

Proof. Since for n ≥ 6 and n ≠ 8 we have {T_i; 1 ≤ i ≤ 4} = {S_n,D_n-2,₂,D_n-3,₃,H₂,_n-3,₂} and the Balaban index has SLC-property, it suffices to compare J (H_n-3,₂,₂) and J (D_n-4,₄) if n ≠ 8, by Lemma 13. In H_n-3,₂,₂ there are five orbits of vertices with value of w equal to 4n-10, 3n-8, 2n-4, n +2 and 2n. Therefore

J(Hn−3,2,2)=(n−1)(1(4n−10)(3n−8)+1(3n−8)(2n−4)+1(2n−4)(n+2)+n−4(n+2)2n).$$\begin{align}& J\left( {{H}_{n-3,2,2}} \right)=\left( n-1 \right)\left( \frac{1}{\sqrt{\left( 4n-10 \right)\left( 3n-8 \right)}}+\frac{1}{\sqrt{\left( 3n-8 \right)\left( 2n-4 \right)}}+\frac{1}{\sqrt{\left( 2n-4 \right)\left( n+2 \right)}} \right. \\ & \left. \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,+\frac{n-4}{\sqrt{\left( n+2 \right)2n}} \right)\,. \\ \end{align}$$

We already know that

J(Dn−4,4)=(n−1)(3(3n−8)(2n−6)+1(2n−6)(n+2)+n−5(n+2)2n).$$J\left( {{D}_{n-4,4}} \right)=\left( n-1 \right)\left( \frac{3}{\sqrt{\left( 3n-8 \right)\left( 2n-6 \right)}}+\frac{1}{\sqrt{\left( 2n-6 \right)\left( n+2 \right)}}+\frac{n-5}{\sqrt{\left( n+2 \right)2n}} \right)\,.$$

Since there is no D_n-4,₄ for n ≤ 7, we have T₅ = H_n-3,₂,₂ if 6 ≤ n ≤ 7. The case n = 8 was checked by a computer and it was found that T₅ = H₂,₅,₂. (In fact, it suffices to check the graphs H_a,_b,_c, and the star convexity rules out all of them except H₂,₅,₂ and H₅,₂,₂, for which J (H₂,₅,₂) > J(H₅,₂,₂) by path-sliding.) Hence, it suffices to consider n ≥ 9.

For n ≥ 18, the following holds

(7)J(Hn−3,2,2)>J(Dn−4,4),$$J\left( {{H}_{n-3,2,2}} \right)>J\left( {{D}_{n-4,4}} \right)\,,$$

which implies that T₅ = H_n-3,₂,₂ for n ≥ 18. Again including a rigorous proof of (7) would be too complicated.

We only show that the difference J (H_n-3,₂,₂)-J(D_n-4,₄) tends to a positive constant. By (4) and (5) we have

limn−∞(J(Hn−3,2,2)−J(Dn−4,4))=112+16+12+12−36−12=1+6−2212=·0.179285>0.$$\begin{align}& \underset{n-\infty }{\mathop{\lim }}\,\left( J\left( {{H}_{n-3,2,2}} \right)-J\left( {{D}_{n-4,4}} \right) \right)=\frac{1}{\sqrt{12}}+\frac{1}{\sqrt{6}}+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{2}}-\frac{3}{\sqrt{6}}-\frac{1}{\sqrt{2}} \\ & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,=\frac{1+\sqrt{6}-2\sqrt{2}}{\sqrt{12}}\overset{\centerdot }{\mathop{=}}\,0.179285>0. \\ \end{align}$$

The difference J (H_n-3,₂,₂)-J(D_n-4,₄) is increasing with n, and we obtain the first four decimals 0:1792 of the above limit when n is of order 37 · 103.

For 9 ≤ n ≤ 17 it holds J(D_n-4,₄) > J(H_n-3,₂,₂), and so T₅ = D_n-4,₄ in these cases.

Now we concentrate on T₆.

Let ν be an invariant with SLC-property. If{Tiv;1≤i≤5}=$\left\{ T_{i}^{v};1\le i\le 5 \right\}=${Sn,Dn−2,2,Dn−3,3,H2,n−3,2,Hn−3,2,2},$\left\{ {{S}_{n}},{{D}_{n-2,2}},{{D}_{n-3,3}},{{H}_{2,n-3,2}},{{H}_{n-3,2,2}} \right\}\,,$thenT6v=Dn−4,4.$T_{6}^{v}={{D}_{n-4,4}}.$

Proof. Analogously as in Lemma 13, T6v$T_{6}^{v}$may be of diameter 3, 4 or 5. By star-convexity D_n-4,₄ is the only candidate among trees of diameter 3. Further, H₃,_n-4,₂ and H₃,_n-5,₃ are the only candidates among caterpillars of diameter 4, but in Lemma 11 we have already found that ν(D_n-4,₄) > ν(H₃,_n-4,₂) and ν(D_n-4,₄) > ν(H₃,_n-5,₃).

If T6v$T_{6}^{v}$has diameter 4 and is not a caterpillar, then the central vertex of T6v$T_{6}^{v}$is adjacent with three distinct vertices of degree at least 2, and every edge-lifting of T6v$T_{6}^{v}$must result in H₂,_n-3,₂ or H_n-3,₂,₂. Consequently, every edge-lifting of T6v$T_{6}^{v}$must result in H₂,_n-3,₂ and T6v$T_{6}^{v}$is R_n. Since in Lemma 13 we derived ν(D_n-4,₄) > ν(R_n), also R_n is out of consideration.

Finally, if T6v$T_{6}^{v}$is a tree of diameter 5, it must be a caterpillar since every edge-lifting of T6v$T_{6}^{v}$results in a caterpillar of diameter 4. If T6v$T_{6}^{v}$has a unique vertex of degree at least 3 then it is H₂,_n-4,₂,₂. However, an edge-lifting of H₂,_n-4,₂,₂ results in H₃,_n-4,₂. Since ν(D_n-4,₄) > ν(H₃,_n-4,₂), we have ν(D_n-4,₄) > ν(H₂,_n-4,₂,₂). On the other hand, if T6v$T_{6}^{v}$has at least two vertices of degree at least 3 then there is an edge-lifting of T6v$T_{6}^{v}$which results in a caterpillar of diameter 4 with at least two vertices of degree at least 3. Since such a caterpillar is not in {Tiv;1≤i≤5},$\left\{ T_{i}^{v};1\le i\le 5 \right\}\,,$also this tree is out of consideration. Therefore, T6v=Dn−4,4.$T_{6}^{v}={{D}_{n-4,4}}.$

The following holds:

T6={P6ifn=6H3,3,2,ifn=7D5,5,ifn=10Hn−3,2,2,ifn∈{8,9}or11≤n≤17Dn−4,4,ifn≥18.$${{T}_{6}}=\left\{ \begin{array}{*{35}{l}}{{P}_{6}} & if\,n=6 \\{{H}_{3,3,2}}, & if\,n=7 \\{{D}_{5,5}}, & if\,n=10 \\{{H}_{n-3,2,2}}, & if\,n\in \left\{ 8,9 \right\}\,or\,11\le n\le 17 \\{{D}_{n-4,4}}, & if\,n\ge 18\,. \\\end{array} \right.$$

Proof. Since for n ≥ 18 we have {T_i; 1 ≤ i ≤ 5} = {S_n, D_n-2,₂,D_n-3,₃,H₂,_n-3,₂,H_n-3,₂,₂} and the Balaban index has SLC-property, T₆ = D_n-4,₄ if n ≥ 18, by Lemma 15. The other cases were solved by a computer. (Analogously as for the case n = 8 in the proof of Proposition 14, for each n it suffices to check the Balaban index of a few graphs.)

In what follows we assume that n ≥ 7, as otherwise T₇ does not exist.

Let ν be an invariant with SLC-property. If{Tiv;1≤i≤6}=$\left\{ T_{i}^{v};1\le i\le 6 \right\}=${Sn,Dn−2,2,Dn−3,3,Dn−4,4,H2,n−3,2,Hn−3,2,2,},$\left\{ {{S}_{n}},{{D}_{n-2,2}},{{D}_{n-3,3}},{{D}_{n-4,4}},{{H}_{2,n-3,2}},{{H}_{n-3,2,2}}, \right\}\,,$then

T7v∈{Dn−5,5,H3,n−4,2,Hn−4,3,2,Hn−4,2,3}.$$T_{7}^{v}\in \left\{ {{D}_{n-5,5}},{{H}_{3,n-4,2}},{{H}_{n-4,3,2}},{{H}_{n-4,2,3}} \right\}\,.$$

Proof. Analogously as in Lemmas 13 and 15, T7v$T_{7}^{v}$may be of diameter 3, 4 or 5. Moreover, in the very same way as in Lemma 15 one can derive that there is no candidate among trees of diameter 5, and the only candidate among trees of diameter 4 which is not a caterpillar is R_n. Further, D_n-5,₅ is the only candidate among trees of diameter 3, so it remains to consider caterpillars H_a,_b,_c of diameter 4. However, if two from a,b,c are at least 5, then ν(H_a,_b,_c) < ν(D_n-5,₅) due to edge-lifting. Analogously, if a ≥ 5 and b +c ≥ 6, then ν(H_a,_b,_c) < ν(D_n-5,₅) due to edge-lifting. Therefore, we have 9 candidates, namely D_n-5,₅, H₃,_n-4,₂, H₄,_n-5,₂, H₃,_n-5,₃, H₄,_n-6,₃, H₄,_n-7,₄, H_n-4,₃,₂, H_n-4,₂,₃ and R_n.

In Lemma 13 we have already shown that ν(H₃,_n-4,₂) > ν(R_n), so R_n is out of consideration. The function ν(H_x,_n-5,_6-x) is strictly convex due to star-convexity, and so ν(D_n-5,₅) > ν(H₄,_n-5,₂) and ν(D_n-5,₅) > n(H₃,_n-5,3). Analogously, ν(D_n-5,₅) > ν(D_n-6,₆) > ν(H₄,_n-6,₃) and ν(D_n-5,₅) > ν(D_n-7,₇) > ν(H₄,_n-7,₄).

Hence, T7v∈{Dn−5,5,$T_{7}^{v}\in \left\{ {{D}_{n-5,5}} \right.,$

H₃,_n-4,₂,H_n-4,₃,₂,H_n-4,₂,₃g.

The following holds:

T7={R7,ifn=7H7,2,2,ifn=10D6,5,ifn=11H3,n−4,2,ifn∈{8,9}orn≥12.$${{T}_{7}}=\left\{ \begin{array}{*{35}{l}}{{R}_{7}}, & if\,n=7 \\{{H}_{7,2,2}}, & if\,n=10 \\{{D}_{6,5}}, & if\,n=11 \\{{H}_{3,n-4,2}}, & if\,n\in \left\{ 8,9 \right\}\,or\,n\ge 12\,. \\\end{array} \right.$$

Proof. Since for n ≥ 8 and n ≠ 10 we have {T_i; 1 ≤ i ≤ 6} = {S_n,D_n-2,₂,D_n-3,₃,D_n-4,₄, H₂,_n-3,₂,H_n-3,₂,₂} and the Balaban index has SLC-property, T₇2 {D_n-5,₅,H₃,_n-4,₂,H_n-4,₃,₂, H_n-4,₂,₃} if n ≥ 8 and n 6= 10, by Lemma 17. In these cases it suffices to compare J(H₃,_n-4,₂), J (H_n-4,₂,₃), J(H_n-4,₃,₂) and J(D_n-5,₅).

By Lemma 6,

J(Dn−5,5)=(n−1)(4(3n−9)(2n−7)+1(2n−7)(n+3)+n−6(n+3)(2n+1)).$$J\left( {{D}_{n-5,5}} \right)=\left( n-1 \right)\left( \frac{4}{\sqrt{\left( 3n-9 \right)\left( 2n-7 \right)}}+\frac{1}{\sqrt{\left( 2n-7 \right)\left( n+3 \right)}}+\frac{n-6}{\sqrt{\left( n+3 \right)\left( 2n+1 \right)}} \right)\,.$$

In H₃,_n-4,₂ there are six orbits of vertices with values of w equal to 3n-4, 2n-2, 3n-6, 2n-4, n +2 and 2n.

Therefore

J(H3,n−4,2)=(n−1)(1(3n−4)(2n−2)+1(2n−2)(n+2)+2(3n−6)(2n−4)+1(2n−4)(n+2)+n−6(n+2)2n).$$\begin{align}& J\left( {{H}_{3,n-4,2}} \right)=\left( n-1 \right)\left( \frac{1}{\sqrt{\left( 3n-4 \right)\left( 2n-2 \right)}}+\frac{1}{\sqrt{\left( 2n-2 \right)\left( n+2 \right)}}+\frac{2}{\sqrt{\left( 3n-6 \right)\left( 2n-4 \right)}} \right. \\ & \left. \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,+\frac{1}{\sqrt{\left( 2n-4 \right)\left( n+2 \right)}}+\frac{n-6}{\sqrt{\left( n+2 \right)2n}} \right)\,. \\ \end{align}$$

In H_n-4,₃,₂ there are also six orbits of vertices with values of w equal to 4n-11, 3n-9, 2n-5, 3n-7, n +3 and 2n+1. Therefore

JHn−<!-- - -->4,3,2=n−<!-- - -->114n−<!-- - -->113n−<!-- - -->9+13n−<!-- - -->92n−<!-- - -->5+12n−<!-- - -->53n−<!-- - -->7+12n−<!-- - -->5n+3+n−<!-- - -->5n+32n+1.$$\matrix{ {} & {J\left( {{H_{n - 4,3,2}}} \right) = \left( {n - 1} \right)\left( {{1 \over {\sqrt {\left( {4n - 11} \right)\left( {3n - 9} \right)} }} + {1 \over {\sqrt {\left( {3n - 9} \right)\left( {2n - 5} \right)} }} + {1 \over {\sqrt {\left( {2n - 5} \right)\left( {3n - 7} \right)} }}} \right.} \cr {} & {\left. { + {1 \over {\sqrt {\left( {2n - 5} \right)\left( {n + 3} \right)} }} + {{n - 5} \over {\sqrt {\left( {n + 3} \right)\left( {2n + 1} \right)} }}} \right).} \cr } $$

Finally, in H_n-4,₂,₃ there are five orbits of vertices with values of w equal to 4n-12, 3n-10, 2n-4, n +4 and 2n+2. Therefore

J(Hn−4,2,3)=(n−1)(2(4n−12)(3n−10)+1(3n−10)(2n−4)+1(2n−4)(n+4)+n−5(n+4)(2n+2)).$$\begin{align}& J\left( {{H}_{n-4,2,3}} \right)=\left( n-1 \right)\left( \frac{2}{\sqrt{\left( 4n-12 \right)\left( 3n-10 \right)}}+\frac{1}{\sqrt{\left( 3n-10 \right)\left( 2n-4 \right)}}+\frac{1}{\sqrt{\left( 2n-4 \right)\left( n+4 \right)}} \right. \\ & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\left. +\frac{n-5}{\sqrt{\left( n+4 \right)\left( 2n+2 \right)}} \right)\,. \\ \end{align}$$

For n ≥ 8, the following holds

(8)J(H3,n−4,2)>J(Hn−4,3,2)>J(Hn−4,2,3).$$J\left( {{H}_{3,n-4,2}} \right)>J\left( {{H}_{n-4,3,2}} \right)>J\left( {{H}_{n-4,2,3}} \right)\,.$$

Again giving a rigorous proof of (8) would be tedious. We only show that each of the differences J (H₃,_n-4,₂) − J (H_n-4,₃,₂) and J (H_n-4,₃,₂)-J(H_n-4,₂,₃) tends to the same positive constant. By (4) and (5) we have

limn→∞(J(H3,n−4,2)−J(Hn−4,3,2))=16+12+26+12−112−16−16−12−12+342=4−22+3346=·0.649903>0$$\begin{align}& \underset{n\to \infty }{\mathop{\lim }}\,\left( J\left( {{H}_{3,n-4,2}} \right)-J\left( {{H}_{n-4,3,2}} \right) \right)=\frac{1}{\sqrt{6}}+\frac{1}{\sqrt{2}}+\frac{2}{\sqrt{6}}+\frac{1}{\sqrt{2}}-\frac{1}{\sqrt{12}}-\frac{1}{\sqrt{6}}-\frac{1}{\sqrt{6}}-\frac{1}{\sqrt{2}} \\ & -\frac{1}{\sqrt{2}}+\frac{3}{4\sqrt{2}}=\frac{4-2\sqrt{2}+3\sqrt{3}}{4\sqrt{6}}\overset{\centerdot }{\mathop{=}}\,0.649903>0 \\ \end{align}$$

and

limn→<!-- ? -->∞<!-- 8 -->JHn−<!-- - -->4,2,3−<!-- - -->JHn−<!-- - -->4,2,3=112+16+16+12−<!-- - -->212−<!-- - -->16−<!-- - -->16+342=4−<!-- - -->22+3346=⋅0.649903>0.$$\begin{align}& \underset{n\to \infty }{\mathop{\lim }}\,\left( J\left( {{H}_{n-4,2,3}} \right)-J\left( {{H}_{n-4,2,3}} \right) \right)=\frac{1}{\sqrt{12}}+\frac{1}{\sqrt{6}}+\frac{1}{\sqrt{6}}+\frac{1}{\sqrt{2}}-\frac{2}{\sqrt{12}}-\frac{1}{\sqrt{6}}-\frac{1}{\sqrt{6}}+\frac{3}{4\sqrt{2}} \\ & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,=\frac{4-2\sqrt{2}+3\sqrt{3}}{4\sqrt{6}}\overset{\centerdot }{\mathop{=}}\,0.649903>0. \\ \end{align}$$

Let us remark that both differences J(H₃,_n-4,₂)-J(H_n-4,₃,₂) and J(H_n-4,₃,₂)-J(H_n-4,₂,₃) are increasing with n, and we obtain the first four decimals 0:6499 of the above limit when n is of order 8 · 104.

Analogously, for n ≥ 12 we have

(9)J(H3,n−4,2)>J(Dn−5,5).$$J\left( {{H}_{3,n-4,2}} \right)>J\left( {{D}_{n-5,5}} \right).$$

Again we only find the limit

limn→∞(J(H3,n−4,2)−J(Dn−5,5))=26+12+16+12−46−12+342=73−446=·0.829188>0.$$\begin{align}& \underset{n\to \infty }{\mathop{\lim }}\,\left( J\left( {{H}_{3,n-4,2}} \right)-J\left( {{D}_{n-5,5}} \right) \right)=\frac{2}{\sqrt{6}}+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{6}}+\frac{1}{\sqrt{2}}-\frac{4}{\sqrt{6}}-\frac{1}{\sqrt{2}}+\frac{3}{4\sqrt{2}} \\ & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,=\frac{7\sqrt{3}-4}{4\sqrt{6}}\overset{\centerdot }{\mathop{=}}\,0.829188>0\,. \\ \end{align}$$

The difference J (H₃,_n-4,₂)-J(D_n-5,₅) is increasing with n, and we obtain the first four decimals 0:8291 of the above limit when n is of order 8 · 104.

Consequently, T₇ = H₃,_n-4,₂ if n ≥ 12. We have T₇ = H₃,_n-4,₂ also if n ϵ {8,9} since in these cases D_n-5,₅ does not exists. For n = 11 the inequality (9) does not hold so in this case T₇ = D_n-5,₅, and the cases n ϵ {7,10} were found by a computer.

We remark that it is possible to continue in this manner, but the situation is more and more complicated. It would be helpful to obtain a further structural statement, not to increase the number of graphs one has to compare.

Our results are summarized in Table 1. We remark that for all n ≤ 17 we found the seven trees with the maximum Balaban index also using the computer program Sage. We first generate all trees on n vertices using the computer program Nauty, and then determine the corresponding extremes in Sage. This is doable only for small values of n (not much bigger than 20) on our computer resources.

Table 1

First seven trees with maximal values of Balaban index.

Observe that

J(Sn)=(n−1)(n−1(n−1)(2n−3)).$$J\left( {{S}_{n}} \right)=\left( n-1 \right)\left( \frac{n-1}{\sqrt{\left( n-1 \right)\left( 2n-3 \right)}} \right)\,.$$

By (4) and (5) we have

limn→∞(J(Sn)−J(H3,n−4,2))=52−16−12−26−12+942=213−1246=·2.487565.$$\begin{align}& \underset{n\to \infty }{\mathop{\lim }}\,\left( J\left( {{S}_{n}} \right)-J\left( {{H}_{3,n-4,2}} \right) \right)=\frac{5}{\sqrt{2}}-\frac{1}{\sqrt{6}}-\frac{1}{\sqrt{2}}-\frac{2}{\sqrt{6}}-\frac{1}{\sqrt{2}}+\frac{9}{4\sqrt{2}} \\ & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,=\frac{21\sqrt{3}-12}{4\sqrt{6}}\overset{\centerdot }{\mathop{=}}\,2.487565. \\ \end{align}$$

Hence, although J(Sn)∼n2,$J\left( {{S}_{n}} \right)\sim \frac{n}{\sqrt{2}}\,,$the difference J (T₁)-J(T₇) is tending to a constant. The same can be noted for the difference J (T₁)-J(D_n-k,_k). Namely, using (4), (5) and Lemma 6 we derive

limn→∞(J(Sn)−J(Dn−k,k))=(k−1)73−446.$$\underset{n\to \infty }{\mathop{\lim }}\,\left( J\left( {{S}_{n}} \right)-J\left( {{D}_{n-k,k}} \right) \right)=\left( k-1 \right)\frac{7\sqrt{3}-4}{4\sqrt{6}}\,.$$

Since the star-convexity implies J (T_k) ≥ J (D_n-k,_k), we obtain that J (T₁)-J(T_k) is at most J (S_n)-J(D_n-k,_k), which tends to a constant. Thus we have the following.

For every k, J(T₁)-J(T_k) is bounded by a constant depending on k but not on n.

In fact, we believe that the difference J (T₁)-J(T_k) is not just bounded by a constant, but it tends to a real number. Hence, we have the following conjecture.

For every k, limn→∞(J(T1)−J(Tk))$\underset{n\to \infty }{\mathop{\lim }}\,\left( J\left( {{T}_{1}} \right)-J\left( {{T}_{k}} \right) \right)$is a constant.