# Further Properties of Trees with Minimal Atom-Bond Connectivity Index

Authors: Jianping Liu; Jinsong Chen
Journal: Abstract and Applied Analysis
 (2014)

---

## Abstract

LetG
=
(
V
,
E
) be a graph the atom-bond connectivity (ABC) index is defined as the sum of weights (
(
d
u
+
d
v
-
2
)
/
d
u
d
v
)
1
/
2 over all edges u
v of G, where d
u denotes the degree of a vertex u of G. In this paper, we determined a few structural features of the trees with minimal ABC index also we characterized the trees with d
i
a
[
T
]
=
2 and minimal ABC index, where [
T
] is induced by the vertices of degree greater than 2 in T and d
i
a
[
T
] is the diameter of [
T
].


---

## Body

## 1. Introduction

LetG
=
(
V
,
E
) be a finite, simple, and undirected graph. The degree of a vertex u
∈
V is denoted by d
u. The atom-bond connectivity (ABC) index is defined as the sum of weights (
(
d
u
+
d
v
-
2
)
/
d
u
d
v
)
1
/
2 over all edges u
v of G; that is,
(1)
ABC
(
G
)
=
∑
u
v
∈
E
(
G
)
‍
d
u
+
d
v
-
2
d
u
d
v
.
The ABC index of a graph was defined by Estrada et al. [1] and it has many chemical applications [1, 2].When examining a topological index, one of the fundamental questions that needs to be answered is for which graphs this index assumes minimal and maximal values and what are these extremal values. In the case of the ABC index, finding the tree for which this index is maximal was relatively easy [3]; it is the star. Eventually, also the trees with second-maximal, third-maximal, and so forth ABC index were determined [4].We [5] have shown that by deleting an edge from any graph, the ABC index decreases. This result implies that among all n-vertex graphs, the complete graph K
n has maximal ABC value. Further, among all connected n-vertex graphs, minimal ABC is achieved by some tree. Thus the n-vertex trees with minimal ABC index are also the n
-vertex connected graphs with minimal ABC index. But the problem of characterizing the n-vertex trees with minimal ABC index turned out to be much more difficult, and a complete solution of this problem is not known. For more results on ABC index see [6–13].In a recent work [6] a combination of computer search and mathematical analysis was undertaken, aimed at elucidating the structure of the minimal ABC trees. And some structural features of the trees with minimal ABC index are given in [7].Lemma 1 (see [6]).
Ifn
≥
10, then the n-vertex tree with minimal ABC index contains at most one pendent path of length k
=
3.Lemma 2 (see [7]).
Ifn
≥
10, then each pendent vertex of the n-vertex tree G with minimalABC index belongs to a pendent path of length k, 2
≤
k
≤
3.By inspecting the structural features of these trees, in [8] the branches B
1
,
…
,
B
5 and B
3
* were given. Let B
i be a branch of tree T formed by attaching i pendant path of length 2 to the vertex v such that the degree of v in T is i
+
1. Let B
i
* be a branch of tree T formed by attaching i
-
1 pendant path of length 2 and a pendant path of length 3 to the vertex v such that the degree of v in T is i
+
1 (see Figure 1). Denote by k
B
i the k union of the branches B
i and by N
(
B
i
) the number of branches B
i in T. From Lemmas 1 and 2, we know all branches in a tree T with minimal ABC index must be of the type B
i or B
i
*, and N
(
B
i
*
)
≤
1, i
=
1,2
,
…. According to Lemma 1, in the following we assume that N
(
B
3
*
)
≤
1 and N
(
B
i
*
)
=
0, for all i
≠
3.Figure 1
The branchesB
i and B
i
*.In [9] the n-vertex minimal ABC trees were determined up to n
=
300 and then a conjecture about the trees with minimal ABC index was presented.Conjecture 3 (see [9]).
LetG be a tree with minimal A
B
C index among all trees of size n. Let T
0, T
1, T
2, T
3, T
4, T
5, and T
6 be the structures depicted in Figure 2.(i)
Ifn
≡
0
(
mod
⁡
7
), n
≥
175 and n
=
7
k
+
28, then G has the structure T
0.
(ii)
Ifn
≡
1
(
mod
⁡
7
), n
≥
64 and n
=
7
k
+
1, then G has the structure T
1.
(iii)
Ifn
≡
2
(
mod
⁡
7
), n
≥
1185 and n
=
7
k
+
9, then G has the structure T
2.
(iv)
Ifn
≡
3
(
mod
⁡
7
), n
≥
80 and n
=
7
k
+
10, then G has the structure T
3.
(v)
Ifn
≡
4
(
mod
⁡
7
), n
≥
312 and n
=
7
k
+
11, then G has the structure T
4.
(vi)
Ifn
≡
5
(
mod
⁡
7
), n
≥
117 and n
=
7
k
+
19, then G has the structure T
5.
(vii)
Ifn
≡
6
(
mod
⁡
7
), n
≥
62 and n
=
7
k
+
6, then G has the structure T
6.Figure 2
Types of trees with minimalABC index correspond to Conjecture 3.In this paper, we determined a few structural features of the trees with minimal ABC index, also we characterized the trees withdia
[
T
]
=
2 and minimal ABC index, where dia
[
T
] is the diameter of [
T
], which was induced by the vertices of degree greater than 2 in T.


## 2. The Structural Features of the Trees with Minimal ABC Index

Now, we are going to determine a few structural features of the trees with minimalABC index.Theorem 4.
Then-vertex tree with minimal A
B
C index does not contain branches B
k and B
k
* (k
≥
6).Proof.
Suppose thatT
k
1 is a tree with minimal ABC index, possessing a branch B
k, k
≥
6. Let u be a vertex of  T
k
1, adjacent to the vertex v, and the degree of u is s. Consider the tree T
k
2 (see Figure 3).
By direct calculation, we have(2)
ABC
(
T
k
1
)
-
ABC
(
T
k
2
)
=
k
+
s
-
1
(
k
+
1
)
s
+
2
-
k
+
s
-
4
(
k
-
2
)
s
-
2
k
-
1
3
(
k
-
2
)
.
If k
=
6, it can be easily checked by computer that
(3)
s
+
5
7
s
+
2
-
s
+
2
4
s
-
2
5
12
>
0
,
that
is
,
ABC
(
T
k
1
)
>
ABC
(
T
k
2
)
.
For the case k
≥
7, if the inequality ABC
(
T
k
1
)
>
ABC
(
T
k
2
) holds, it implies that
(4)
k
+
s
-
1
(
k
+
1
)
s
+
2
+
2
2
k
+
2
s
-
2
(
k
+
1
)
s
>
k
+
s
-
4
(
k
-
2
)
s
+
4
(
k
-
1
)
3
(
k
-
2
)
+
4
(
k
-
1
)
(
k
+
s
-
4
)
(
k
-
2
)
3
s
.
By elementary calculation, this inequality can be transformed to
(5)
3
(
k
-
2
)
(
k
+
s
-
1
)
+
6
s
(
k
+
1
)
(
k
-
2
)
-
3
(
k
+
1
)
(
k
+
s
-
4
)
-
4
s
(
k
+
1
)
(
k
-
1
)
>
4
(
k
+
1
)
3
s
(
k
-
1
)
(
k
+
s
-
4
)
-
6
(
k
-
2
)
s
(
k
+
1
)
(
2
k
+
2
s
-
2
)
.
That is,
(6)
2
k
2
s
-
6
k
s
-
17
s
+
18
+
6
(
k
-
2
)
×
s
(
k
+
1
)
(
2
k
+
2
s
-
2
)
>
4
(
k
+
1
)
3
s
(
k
-
1
)
(
k
+
s
-
4
)
.
By squaring the above relation and rearranging, we get
(7)
(
4
k
4
s
2
-
196
k
2
s
2
)
+
(
252
k
s
2
-
1092
s
)
+
(
24
k
4
s
-
144
k
3
s
)
+
(
528
k
2
s
-
72
k
s
)
+
625
s
2
+
324
+
(
12
2
(
k
-
2
)
(
2
k
2
s
-
6
k
s
-
17
s
+
18
)
×
(
k
+
1
)
s
(
k
+
s
-
1
)
-
100
k
2
s
2
)
>
0
.
Since the function
(8)
g
(
k
,
s
)
=
12
2
(
k
-
2
)
(
2
k
2
s
-
6
k
s
-
17
s
+
18
)
×
(
k
+
1
)
s
(
k
+
s
-
1
)
-
100
k
2
s
2
.
>
16
(
k
-
2
)
(
2
k
2
-
6
k
-
17
)
×
k
+
1
s
2
-
100
k
2
s
2
>
0
(
as
k
≥
7
,
s
≥
3
)
,
and it holds that
(9)
4
k
4
s
2
-
196
k
2
s
2
>
0
,
252
k
s
2
-
1092
s
>
0
,
24
k
4
s
-
144
k
3
s
>
0
,
528
k
2
s
-
72
k
s
>
0
(
as
k
≥
7
,
s
≥
3
)
,
thus, we have
(10)
ABC
(
T
k
1
)
>
ABC
(
T
k
2
)
,
for
k
≥
7
.
In the same way, we can prove that then-vertex tree with minimal ABC index does not contain branch B
k
* (k
≥
6).
The proof is complete.Figure 3Note that Theorem4 holds for all n-vertex trees with minimal ABC index.Theorem 5.
LetT be a tree with minimal A
B
C index, then every vertex of T must not be connected with both B
2 and B
4.Proof.
Suppose thatT
1 is a tree with minimal ABC index; let u be a vertex of T
1, which is connected with both B
2 and B
4, and the degree of u is s
(
s
≥
3
). Construct the tree T
2 by deleting the edge v
2
w and connecting w with v
1 (see Figure 4).
The transformationT
1
→
T
2 causes the following change of the ABC index:
(11)
ABC
(
T
1
)
-
ABC
(
T
2
)
=
s
+
3
5
s
+
s
+
1
3
s
-
2
s
+
2
4
s
.
If the inequality ABC
(
T
1
)
>
ABC
(
T
2
) holds, it implies that
(12)
s
+
3
5
s
+
s
+
1
3
s
+
2
(
s
+
1
)
(
s
+
3
)
15
s
2
>
s
+
2
s
.
By elementary calculation, this inequality can be transformed to
(13)
11
s
2
+
16
s
-
76
>
0
(
s
≥
3
)
.
Thus we have ABC
(
T
1
)
>
ABC
(
T
2
), for s
≥
3.
The proof is complete.Figure 4Theorem 6.
LetT be a tree with minimal A
B
C index; then every vertex of T must not be connected with both B
1 and 2
B
4.Proof.
Suppose thatT
3 is a tree with minimal ABC index; let u be a vertex of T
3, which is connected with both B
1 and 2
B
4, and the degree of u is s (obviously s
≥
3). Construct the tree T
4 by deleting the edges v
2
w
2, v
3
w
3 and adding the edges w
1
w
2, v
1
w
3 (see Figure 5).
The transformationT
3
→
T
4 causes the following change of the ABC index:
(14)
ABC
(
T
3
)
-
ABC
(
T
4
)
=
2
2
+
2
s
+
3
5
s
-
s
+
1
3
s
-
2
s
+
2
4
s
.
If the inequality ABC
(
T
3
)
>
ABC
(
T
4
) holds, it implies that
(15)
1
2
+
4
(
s
+
3
)
5
s
+
2
2
(
s
+
3
)
5
s
>
4
s
+
7
3
s
+
2
s
s
2
+
3
s
+
2
3
.
That is
(16)
1
2
+
4
(
s
+
3
)
5
s
+
2
2
(
s
+
3
)
5
s
-
4
s
+
7
3
s
>
2
s
s
2
+
3
s
+
2
3
.
By squaring the above relation and rearranging, we get
(17)
(
s
-
2
)
(
1198
+
(
241
-
24
(
10
s
+
30
)
/
s
)
s
)
900
s
2
>
0
(
s
≥
3
)
.
Thus we have ABC
(
T
3
)
>
ABC
(
T
4
), for s
≥
3, and the proof is complete.Figure 5Theorem 7.
LetT be a tree with minimal A
B
C index; then every vertex of T must not be connected with 7
B
4.Proof.
Suppose thatT
7 is a tree with minimal ABC index, possessing a vertex u in T
7 connected with 7
B
4 (see Figure 6). Let U
=
{
v
1
,
v
2
,
…
,
v
s
} be the set of adjacent vertices to u. Let d
1
,
d
2
,
…
,
d
s be the degree of v
1
,
v
2
,
…
,
v
s, respectively. We consider the tree T
8 shown in Figure 6.
Here we are going to show thatABC
(
T
7
)
-
ABC
(
T
8
)
>
0, for any s
≥
7.
Consider(18)
ABC
(
T
7
)
-
ABC
(
T
8
)
=
7
s
+
3
5
s
+
2
-
9
s
+
4
4
(
s
+
2
)
+
∑
i
=
8
s
(
s
+
d
i
-
2
s
d
i
-
s
+
d
i
(
s
+
2
)
d
i
)
,
for any d
i
≥
2, (
s
+
d
i
-
2
)
/
(
s
d
i
)
-
(
s
+
d
i
)
/
(
(
s
+
2
)
d
i
)
>
0.
Now we are going to show that7
(
s
+
3
)
/
(
5
s
)
+
2
>
9
(
s
+
4
)
/
4
(
s
+
2
); that is
(19)
49
(
s
+
3
)
5
s
+
2
+
14
2
(
s
+
3
)
5
s
>
81
(
s
+
4
)
4
(
s
+
2
)
.
By elementary calculation, this inequality can be transformed to
(20)
2799
s
4
+
30240
s
3
+
585648
s
2
+
1693440
s
-
1382976
>
0
.
The largest root of the above polynomial is0.660387; therefore, the value of the above polynomial is positive for s
>
0.660387.
Thus we haveABC
(
T
7
)
>
ABC
(
T
8
), and the proof is complete.Figure 6Theorem 8.
LetT be a tree with minimal A
B
C index; then every vertex of T must not be connected with 2
B
5.Proof.
Suppose thatT
5
1 is a tree with minimal ABC index, possessing a vertex connected with 2
B
5. Let u be the vertex of T
5
1, adjacent to the vertices v
1 and v
2, and the degree of u is s (s
≥
3). Consider the tree T
5
2 (see Figure 7).
The transformationT
5
1
→
T
5
2 causes the following change of the ABC index:
(21)
ABC
(
T
5
1
)
-
ABC
(
T
5
2
)
=
2
s
+
4
6
s
+
2
-
s
+
2
4
s
-
s
+
3
5
s
-
2
6
15
.
It can be easily checked by computer that ABC
(
T
5
1
)
>
ABC
(
T
5
2
), for s
≥
3.
The proof is complete.Figure 7


## 3. The MinimalABC Indices of Trees with Order n and d
i
a
[
T
]
=
2

Denote by[
T
] the subgraph of T induced by its vertices of degree greater than 2. For a connected graph G, the diameter of G, denoted by dia
G, is the length of a longest path of G.Lemma 9 (see [7]).
LetT be an n-vertex (
n
≥
10
) tree with minimal A
B
C index; then [
T
] is a tree.Note that the structuresT
i in Conjecture 3 have dia
[
T
i
]
=
2 (i
=
0,1
,
2,3
,
5,6). Let T
n
,
2 be the set of n-vertex trees T with dia
[
T
]
=
2.Now we will characterize the trees withdia
[
T
]
=
2 and minimal ABC index, which partially solve Conjecture 3.Lemma 10.
LetT
∈
T
n
,
2 be a tree with minimal A
B
C index; then T does not contain B
5.Proof.
LetT
5
3
∈
T
n
,
2 be a tree with minimal ABC index. By Theorems 7 and 8, T
5
3 contains at most 6
B
4, 1
B
5; hence, for n
>
65, T
5
3 must contain B
3. Suppose that T
5
3 possesses B
5; then we can construct the tree T
5
4 by deleting the edge v
1
w and adding the edge v
2
w (see Figure 8).
The transformationT
5
3
→
T
5
4 causes the following change of the ABC index:
(22)
ABC
(
T
5
3
)
-
ABC
(
T
5
4
)
=
d
u
+
4
6
d
u
+
d
u
+
2
4
d
u
-
2
d
u
+
3
5
d
u
.
It can be easily checked that ABC
(
T
5
3
)
>
ABC
(
T
5
4
), for d
u
≥
3.
The proof is complete.Figure 8Lemma 11.
LetT
∈
T
n
,
2 be a tree with minimal A
B
C index; if the maximum degree Δ
≥
24, then T must not contain k
B
2 (k
≥
3).Proof.
Suppose thatT
5
∈
T
n
,
2 is a tree with minimal ABC index, possessing 3
B
2 (see Figure 9). Let u be the vertex with maximum degree of T
5, adjacent to the vertices v
1, v
2, and v
3, and the degree of u is s
+
1. Construct the tree T
6 by deleting the edges v
3
w
1 and u
v
3 and adding the edges v
1
w
1 and v
2
v
3. Let U
=
{
v
1
,
v
2
,
…
,
v
s
+
1
} be a set of adjacent vertices to u. Let d
1
,
d
2
,
…
,
d
s
+
1 be the degree of v
1
,
v
2
,
…
,
v
s
+
1, respectively.
The transformationT
5
→
T
6 causes the following change of the ABC index:
(23)
ABC
(
T
5
)
-
ABC
(
T
6
)
=
3
s
+
2
3
(
s
+
1
)
-
2
s
+
2
4
s
-
2
2
+
∑
i
=
4
s
+
1
(
s
+
d
i
-
1
(
s
+
1
)
d
i
-
s
+
d
i
-
2
s
d
i
)
.
By Theorems 4 and 5, Lemma 10, and noticing that T
∈
T
n
,
2, we know that d
i
=
2,3 or 4.
And consider(24)
s
+
3
4
(
s
+
1
)
-
s
+
2
4
s
=
min
⁡
d
i
=
2,3
,
4
⁡
(
s
+
d
i
-
1
(
s
+
1
)
d
i
-
s
+
d
i
-
2
s
d
i
)
.
Putting this in the above expression, we get
(25)
ABC
(
T
5
)
-
ABC
(
T
6
)
≥
3
s
+
2
3
(
s
+
1
)
-
2
s
+
2
4
s
-
2
2
+
(
s
-
2
)
(
s
+
3
4
(
s
+
1
)
-
s
+
2
4
s
)
=
3
s
+
2
3
(
s
+
1
)
+
(
s
-
2
)
s
+
3
4
(
s
+
1
)
-
(
s
2
s
+
2
s
+
2
2
)
.
If the inequality ABC
(
T
5
)
>
ABC
(
T
6
) holds, it implies that
(26)
3
(
s
+
2
)
s
+
1
+
(
s
-
2
)
2
(
s
+
3
)
4
(
s
+
1
)
+
s
-
2
s
+
1
3
(
s
+
2
)
(
s
+
3
)
>
s
(
s
+
2
)
4
+
1
2
+
s
(
s
+
2
)
2
.
By elementary calculation, this inequality can be transformed to
(27)
2
(
s
-
2
)
3
(
s
+
2
)
(
s
+
3
)
>
2
s
2
-
17
+
(
s
+
1
)
2
s
(
s
+
2
)
.
By squaring the above relation and rearranging for two times, we get
(28)
s
8
-
20
s
7
-
86
s
6
+
248
s
5
+
956
s
4
-
430
s
3
-
2183
s
2
-
1130
s
+
1
4
>
0
.
The largest root of the above polynomial is23.1742; therefore, the value of the above polynomial is positive for s
>
23.1742. Thus we have ABC
(
T
5
)
>
ABC
(
T
6
) for s
≥
24, and the proof is complete.Figure 9Lemma 12.
LetT
∈
T
n
,
2 be a tree with minimal A
B
C index; if the maximum degree Δ
≥
13, then T must not contain B
1.Proof.
Suppose thatT
9
∈
T
n
,
2 is a tree with maximum degree Δ
≥
13 and minimal ABC index, possessing k
B
1
(
k
≥
1
) (see Figure 10). By Theorem 6 and Lemma 11, we have N
(
B
2
)
≤
2 and N
(
B
4
)
≤
1. Thus B
3 in T
9 must be contained.
Letu be the vertex with maximum degree s in T
9 and let U
=
{
v
1
,
v
2
,
…
,
v
s
} be a set of adjacent vertices to u. Let d
1
,
d
2
,
…
,
d
s be the degree of v
1
,
v
2
,
…
,
v
s, respectively. Since T
9
∈
T
n
,
2 and by Theorem 4 and Lemma 10, we have d
i
=
2,3
,
4, or 5. Construct the tree T
10 by deleting the edge u
v
k and adding the edge v
k
+
1
v
k to T
9.
The transformationT
9
→
T
10 causes the following change of the ABC index:
(29)
ABC
(
T
9
)
-
ABC
(
T
10
)
=
∑
i
=
k
+
2
s
(
d
i
+
s
-
2
d
i
s
-
d
i
+
s
-
3
d
i
(
s
-
1
)
)
+
(
s
+
2
4
s
-
s
+
2
5
(
s
-
1
)
)
=
N
(
B
2
)
(
s
+
1
3
s
-
s
3
(
s
-
1
)
)
+
N
(
B
4
)
(
s
+
3
5
s
-
s
+
2
5
(
s
-
1
)
)
+
(
s
-
k
-
1
-
N
(
B
2
)
-
N
(
B
4
)
)
×
(
s
+
2
4
s
-
s
+
1
4
(
s
-
1
)
)
+
(
s
+
2
4
s
-
s
+
2
5
(
s
-
1
)
)
.
If the inequalityABC
(
T
9
)
>
ABC
(
T
10
) holds, it implies that
(30)
s
+
2
4
s
-
s
+
2
5
(
s
-
1
)
>
N
(
B
2
)
(
s
3
(
s
-
1
)
-
s
+
1
3
s
)
+
N
(
B
4
)
(
s
+
2
5
(
s
-
1
)
-
s
+
3
5
s
)
+
(
s
-
k
-
1
-
N
(
B
2
)
-
N
(
B
4
)
)
×
(
s
+
1
4
(
s
-
1
)
-
s
+
2
4
s
)
≜
f
(
s
,
k
)
.
Note that N
(
B
2
)
≤
2, N
(
B
4
)
≤
1, k
≥
1, and
(31)
s
3
(
s
-
1
)
-
s
+
1
3
s
<
s
+
1
4
(
s
-
1
)
-
s
+
2
4
s
<
s
+
2
5
(
s
-
1
)
-
s
+
3
5
s
.
We have, f
(
s
,
k
)
≤
(
(
s
+
2
)
/
(
5
(
s
-
1
)
)
-
(
s
+
3
)
/
(
5
s
)
)
+
(
s
-
3
)
(
(
s
+
1
)
/
(
4
(
s
-
1
)
)
-
(
s
+
2
)
/
(
4
s
)
).
Now we are going to show that(32)
s
+
2
4
s
-
s
+
2
5
(
s
-
1
)
>
(
s
+
2
5
(
s
-
1
)
-
s
+
3
5
s
)
+
(
s
-
3
)
(
s
+
1
4
(
s
-
1
)
-
s
+
2
4
s
)
.
That is,
(33)
(
s
-
2
)
s
+
2
4
s
-
2
s
+
2
5
(
s
-
1
)
>
(
s
-
3
)
s
+
1
4
(
s
-
1
)
-
s
+
3
5
s
.
By squaring the above relation and rearranging for two times, we get
(34)
8
5
(
s
-
3
)
(
5
s
-
4
)
(
2
s
2
-
s
+
7
)
s
(
s
-
1
)
(
s
+
1
)
(
s
+
3
)
>
140
s
6
+
180
s
5
-
2709
s
4
+
1734
s
3
+
2151
s
2
-
776
s
-
784
.
Sinces
(
s
-
1
)
(
s
+
1
)
(
s
+
3
)
>
(
s
+
0.6
)
2 (for s
≥
7) and the largest root of the following polynomial is 12.9172,
(35)
8
5
(
s
-
3
)
(
5
s
-
4
)
(
2
s
2
-
s
+
7
)
(
s
+
0.6
)
2
-
140
s
6
-
180
s
5
+
2709
s
4
-
1734
s
3
-
2151
s
2
+
776
s
+
784
=
0
.
Therefore the value of the above polynomial is positive fors
>
12.9172. Thus we have ABC(
T
9
)
> ABC(
T
10
) for s
≥
13 and the proof is complete.Figure 10Theorem 13.
LetT
∈
T
n
,
2 be a tree with minimal ABC index and the maximum degree Δ
≥
24. Let T
0, T
1, T
2, T
3, T
5, and T
6 be the structures depicted in Figure 2.(i)
Ifn
≡
0
(
mod
⁡
7
), n
≥
175 and n
=
7
k
+
28, then T has the structure T
0.
(ii)
Ifn
≡
1
(
mod
⁡
7
), n
≥
169 and n
=
7
k
+
1, then T has the structure T
1.
(iii)
Ifn
≡
2
(
mod
⁡
7
), n
≥
1185 and n
=
7
k
+
9, then T has the structure T
2.
(iv)
Ifn
≡
3
(
mod
⁡
7
), n
≥
171 and n
=
7
k
+
10, then T has the structure T
3.
(v)
Ifn
≡
4
(
mod
⁡
7
), n
≥
2020 and n
=
7
k
+
11, then T has the structure T
4
′ depicted in Figure 11(b).
(vi)
Ifn
≡
5
(
mod
⁡
7
), n
≥
173 and n
=
7
k
+
19, then T has the structure T
5.
(vii)
Ifn
≡
6
(
mod
⁡
7
), n
≥
167 and n
=
7
k
+
6, then T has the structure T
6.(a)
The minimal ABC treeT in T
n
,
2
(b)
T
4
′Proof.
LetT
∈
T
n
,
2 be a tree with minimal ABC index. From Lemmas 1 and 2, we know all branches of T must be of the type B
i or B
i
*, i
=
1,2
,
…. And from Theorem 4 and Lemmas 10 and 12, we know all branches of T must be of the type B
i or B
i
*, i
=
2,3
,
4.
Then the minimalABC tree T
∈
T
n
,
2 has
(36)
n
=
1
+
5
N
(
B
2
)
+
7
N
(
B
3
)
+
9
N
(
B
4
)
+
x
vertices, where x
∈
{
0,1
} counts the pendent paths of length 3.
From above we see that the treeT
∈
T
n
,
2 with minimal ABC index and x
=
0 must possess the structure as shown in Figure 11(a). It is easy to see that
(37)
ABC
(
T
)
=
N
(
B
2
)
d
u
+
1
3
d
u
+
N
(
B
3
)
d
u
+
2
4
d
u
+
N
(
B
4
)
d
u
+
3
5
d
u
+
(
n
-
1
-
N
(
B
2
)
-
N
(
B
3
)
-
N
(
B
4
)
)
2
2
.
Putting (36) in the above equation, we have
(38)
f
(
D
)
≜
ABC
(
T
)
=
N
(
B
2
)
d
u
+
1
3
d
u
+
N
(
B
3
)
d
u
+
2
4
d
u
+
N
(
B
4
)
d
u
+
3
5
d
u
+
(
4
N
(
B
2
)
+
6
N
(
B
3
)
+
8
N
(
B
4
)
+
x
)
2
2
,
where d
u
=
Δ
=
N
(
B
2
)
+
N
(
B
3
)
+
N
(
B
4
) and D
=
(
N
(
B
2
)
,
N
(
B
3
)
,
N
(
B
4
)
,
x
).
From Lemma11 and Theorems 5 and 7, we get
(39)
N
(
B
2
)
∈
{
0,1
,
2
}
,
N
(
B
4
)
∈
{
0,1
,
2,3
,
4,5
,
6
}
,
N
(
B
2
)
N
(
B
4
)
=
0
.
Note that the parametersn, N
(
B
2
), N
(
B
3
), N
(
B
4
), and x in (36) are nonnegative integers.
Consider(i)
n
≡
0
(
mod
⁡
7
) and n
=
7
k
+
28.
Case  1
.1. If N
(
B
2
)
=
0, then n
=
1
+
7
N
(
B
3
)
+
9
N
(
B
4
)
+
x
≡
0
(
mod
⁡
7
).
Thus,9
N
(
B
4
)
+
x
+
1
≡
0
(
mod
⁡
7
), we get N
(
B
4
)
=
3, x
=
0 or N
(
B
4
)
=
6, x
=
1.
That is,D
=
(
0
,
(
n
/
7
)
-
4,3
,
0
)
=
(
0
,
k
,
3,0
) or (
0
,
(
n
/
7
)
-
8,6
,
1
)
=
(
0
,
k
-
4,6
,
1
).
Case  1.2. If N
(
B
2
)
=
1, then N
(
B
4
)
=
0, n
=
1
+
5
+
7
N
(
B
3
)
+
x
≡
0
(
mod
⁡
7
); we get x
=
1.
That is,D
=
(
1
,
(
n
/
7
)
-
1,0
,
1
)
=
(
1
,
k
+
3,0
,
1
).
Case  1.3. If N
(
B
2
)
=
2, then N
(
B
4
)
=
0 and n
=
11
+
7
N
(
B
3
)
+
x
≡
0
(
mod
⁡
7
); there is no solution.
Comparing the valuesf
(
0
,
k
,
3,0
), f
(
0
,
k
-
4,6
,
1
), and f
(
1
,
k
+
3,0
,
1
) and noting that Δ
≥
24, we get that
(40)
f
(
0
,
k
,
3,0
)
=
k
k
+
5
4
(
k
+
3
)
+
3
k
+
6
5
(
k
+
3
)
+
(
3
k
+
12
)
2
is the smallest one (k
≥
21); the result (i) follows.
Consider(ii)
n
≡
1
(
mod
⁡
7
) and n
=
7
k
+
1.
Case  2.1. If N
(
B
2
)
=
0, then 9
N
(
B
4
)
+
x
+
1
≡
1
(
mod
⁡
7
).
We getN
(
B
4
)
=
0
,
x
=
0 or N
(
B
4
)
=
3
,
x
=
1.
That is,D
=
(
0
,
k
,
0,0
) or (
0
,
k
-
4,3
,
1
).
Case  2
.2. If N
(
B
2
)
=
1, then N
(
B
4
)
=
0 and n
=
1
+
5
+
7
N
(
B
3
)
+
x.
Thus5
+
x
≡
0
(
mod
⁡
7
); there is no solution.
Case  2
.3. If N
(
B
3
)
=
2, then N
(
B
4
)
=
0 and n
=
1
+
10
+
7
N
(
B
3
)
+
x.
Thus10
+
x
≡
0
(
mod
⁡
7
); there is no solution.
Comparing the valuesf
(
0
,
k
,
0,0
), f
(
0
,
k
-
4,3
,
1
), we get that
(41)
f
(
0
,
k
,
0,0
)
=
k
k
+
2
4
k
+
3
k
2
is the smallest one (k
≥
24); the result (ii) follows.
Consider(iii)
n
≡
2
(
mod
⁡
7
) and n
=
7
k
+
9.
Case  3.1. If N
(
B
2
)
=
0, then n
=
1
+
7
N
(
B
3
)
+
9
N
(
B
4
)
+
x
≡
2
(
mod
⁡
7
).
We getN
(
B
4
)
=
0, x
=
1 or N
(
B
4
)
=
4, x
=
0.
That is,D
=
(
0
,
k
+
1,0
,
1
) or (
0
,
k
-
4,4
,
0
).
Case  3.2. If N
(
B
2
)
=
1, then N
(
B
4
)
=
0 and n
=
1
+
5
+
7
N
(
B
3
)
+
x.
Thus6
+
x
≡
2
(
mod
⁡
7
); there is no solution.
Case  3.3. If N
(
B
2
)
=
2, then N
(
B
4
)
=
0 and n
=
1
+
10
+
7
N
(
B
3
)
+
x.
Thus11
+
x
≡
2
(
mod
⁡
7
); there is no solution.
Comparing the valuesf
(
0
,
k
+
1,0
,
1
), f
(
0
,
k
-
4,4
,
0
), we get that
(42)
f
(
0
,
k
-
4,4
,
0
)
=
(
k
-
4
)
k
+
2
4
k
+
4
k
+
3
5
k
+
(
3
k
+
4
)
2
is the smallest one (k
≥
168); the result (iii) follows.
Consider(iv)
n
≡
3
(
mod
⁡
7
) and n
=
7
k
+
10.
Case  4
.1. If N
(
B
2
)
=
0, then n
=
1
+
7
N
(
B
3
)
+
9
N
(
B
4
)
+
x
≡
3
(
mod
⁡
7
).
We getN
(
B
4
)
=
1, x
=
0 or N
(
B
4
)
=
4, x
=
1.
That is,D
=
(
0
,
k
,
1,0
) or (
0
,
k
-
4,4
,
1
).
Case  4
.2. If N
(
B
2
)
=
1, then N
(
B
4
)
=
0 and n
=
1
+
5
+
7
N
(
B
3
)
+
x.
Thus6
+
x
≡
3
(
mod
⁡
7
); there is no solution.
Case  4.3. If N
(
B
2
)
=
2, then N
(
B
4
)
=
0 and n
=
1
+
10
+
7
N
(
B
3
)
+
x.
Thus11
+
x
≡
3
(
mod
⁡
7
); there is no solution.
Comparing the valuesf
(
0
,
k
,
1,0
), f
(
0
,
k
-
4,4
,
1
), we get that
(43)
f
(
0
,
k
,
1,0
)
=
k
k
+
3
4
(
k
+
1
)
+
k
+
4
5
(
k
+
1
)
+
(
3
k
+
4
)
2
is the smallest one (k
≥
23); the result (iv) follows.
Consider(v)
n
≡
4
(
mod
⁡
7
) and n
=
7
k
+
11.
Case  5.1. If N
(
B
2
)
=
0, then n
=
1
+
7
N
(
B
3
)
+
9
N
(
B
4
)
+
x
≡
4
(
mod
⁡
7
).
We getN
(
B
4
)
=
1, x
=
1 or N
(
B
4
)
=
5, x
=
0.
That is,D
=
(
0
,
k
,
1,1
) or (
0
,
k
-
5,5
,
0
).
Case  5.2. If N
(
B
2
)
=
1, then N
(
B
4
)
=
0, n
=
1
+
5
+
7
N
(
B
3
)
+
x.
Thus6
+
x
≡
4
(
mod
⁡
7
); there is no solution.
Case  5
.3. If N
(
B
2
)
=
2, then N
(
B
4
)
=
0 and n
=
1
+
10
+
7
N
(
B
3
)
+
x.
Thus11
+
x
≡
4
(
mod
⁡
7
), we get x
=
0.
That is,D
=
(
2
,
k
,
0,0
).
Comparing the valuesf
(
0
,
k
,
1,1
), f
(
0
,
k
-
5,5
,
0
), and f
(
2
,
k
,
0,0
), we get that
(44)
f
(
2
,
k
,
0,0
)
=
k
k
+
4
4
(
k
+
2
)
+
2
k
+
3
3
(
k
+
2
)
+
(
3
k
+
4
)
2
is the smallest one (k
=
22,23
,
…
,
286) and that
(45)
f
(
0
,
k
-
5,5
,
0
)
=
(
k
-
5
)
k
+
2
4
k
+
5
k
+
3
5
k
+
(
3
k
+
5
)
2
is the smallest one (k
≥
287). The result (v) follows.
Consider(vi)
n
≡
5
(
mod
⁡
7
) and n
=
7
k
+
19.
Case  6.1. If N
(
B
2
)
=
0, then n
=
1
+
7
N
(
B
3
)
+
9
N
(
B
4
)
+
x
≡
5
(
mod
⁡
7
).
We getN
(
B
4
)
=
2, x
=
0 or N
(
B
4
)
=
5, x
=
1.
That is,D
=
(
0
,
k
,
2,0
) or (
0
,
k
-
4,5
,
1
).
Case  6.2. If N
(
B
2
)
=
1, then N
(
B
4
)
=
0 and n
=
1
+
5
+
7
N
(
B
3
)
+
x.
Thus6
+
x
≡
5
(
mod
⁡
7
); there is no solution.
Case  6.3. If N
(
B
2
)
=
2, then N
(
B
4
)
=
0 and n
=
1
+
10
+
7
N
(
B
3
)
+
x.
Thus11
+
x
≡
5
(
mod
⁡
7
), we get x
=
1.
That is,D
=
(
2
,
k
+
1,0
,
1
).
Comparing the valuesf
(
0
,
k
,
2,0
), f
(
0
,
k
-
4,5
,
1
), and f
(
2
,
k
+
1,0
,
1
), we get that
(46)
f
(
0
,
k
,
2,0
)
=
k
k
+
4
4
(
k
+
2
)
+
2
k
+
5
5
(
k
+
2
)
+
(
3
k
+
8
)
2
is the smallest one (k
≥
22); the result (vi) follows.
Consider(vii)
n
≡
6
(
mod
⁡
7
) and n
=
7
k
+
6.
Case  7.1. If N
(
B
2
)
=
0, then n
=
1
+
7
N
(
B
3
)
+
9
N
(
B
4
)
+
x
≡
6
(
mod
⁡
7
).
We getN
(
B
4
)
=
2, x
=
1 or N
(
B
4
)
=
6, x
=
0.
That is,D
=
(
0
,
k
-
2,2
,
1
) or (
0
,
k
-
7,6
,
0
).
Case  7.2. If N
(
B
2
)
=
1, then N
(
B
4
)
=
0 and n
=
1
+
5
+
7
N
(
B
3
)
+
x.
Thus6
+
x
≡
6
(
mod
⁡
7
), we get x
=
0.
That is,D
=
(
1
,
k
,
0,0
).
Case  7.3. If N
(
B
2
)
=
2, then N
(
B
4
)
=
0 and n
=
1
+
10
+
7
N
(
B
3
)
+
x.
Thus11
+
x
≡
6
(
mod
⁡
7
); there is no solution.
Comparing the valuesf
(
0
,
k
-
2,2
,
1
), f
(
0
,
k
-
7,6
,
0
), and f
(
1
,
k
,
0,0
), we get that
(47)
f
(
1
,
k
,
0,0
)
=
k
k
+
3
4
(
k
+
1
)
+
k
+
2
3
(
k
+
1
)
+
(
3
k
+
2
)
2
is the smallest one (k
≥
23); the result (vii) follows.In [13], the authors also gave a similar result as Theorem 13 (in [13], a tree T
∈
T
n
,
2 without pendent path of length 3 is called a proper Krag tree), but we do it independently and the methods are also different.



---

*Source: 609208-2014-06-19.xml*