# The Hyper-Wiener Index of Trees of Ordern with Diameter d

Authors: Gaixiang Cai; Guidong Yu; Jinde Cao; Ahmad Alsaedi; Fuad Alsaadi
Journal: Discrete Dynamics in Nature and Society
 (2016)

---

## Abstract

The hyper-Wiener index is a kind of extension of the Wiener index, used for predicting physicochemical properties of organic compounds. The hyper-Wiener indexW
W
(
G
) is defined as W
W
(
G
)
=
1
/
2
∑
u
,
v
∈
V
G
d
G
u
,
v
+
d
G
2
u
,
v with the summation going over all pairs of vertices in G, and d
G
u
,
v denotes the distance of the two vertices u and v in the graph G. In this paper, we obtain the second-minimum hyper-Wiener indices among all the trees with n vertices and diameter d and characterize the corresponding extremal graphs.


---

## Body

## 1. Introduction

LetG be a simple graph of order n with vertex set V
G and edge set E
G. The distance between two vertices u
,
v of G, denoted by d
G
u
,
v or d
u
,
v, is defined as the minimum length of the paths between u and v in G. The diameter of a graph G is the maximum distance between any two vertices of G.The Wiener index of a graphG, denoted by W
(
G
), is one of the oldest topological indexes, which was first introduced by Wiener [1] in 1947. It is defined as W
(
G
)
=
∑
u
,
v
∈
V
(
G
)
d
G
(
u
,
v
) where the summation goes over all pairs of vertices of G. The hyper-Wiener index of acyclic graphs was introduced by Randić in 1993 [2]. Then Klein et al. [3] extended the definition for all connected graphs, as a generalization of the Wiener index. Similar to the symbol W
(
G
) for the Wiener index, the hyper-Wiener index is traditionally denoted by W
W
(
G
). The hyper-Wiener index of a graph G is defined as (1)
W
W
G
=
1
2
∑
u
,
v
∈
V
G
d
G
u
,
v
+
∑
u
,
v
∈
V
G
d
G
2
u
,
v
.LetS
(
G
)
=
∑
u
,
v
∈
V
(
G
)
d
G
2
(
u
,
v
)
. Then (2)
W
W
G
=
1
2
W
G
+
1
2
S
G
. We denote D
G
(
u
)
=
∑
v
∈
V
(
G
)
d
G
(
u
,
v
)
,
D
D
G
(
u
)
=
∑
v
∈
V
(
G
)
d
G
2
(
u
,
v
), and then (3)
W
G
=
1
2
∑
u
∈
V
G
D
G
u
,
S
G
=
1
2
∑
u
∈
V
G
D
D
G
u
.Recently, the properties and uses of the hyper-Wiener index have received a lot of attention. Feng and Ilić [4] studied hyper-Wiener indices of graphs with given matching number. Feng et al. [5] researched the hyper-Wiener index of unicyclic graphs. Feng et al. [6] discussed the hyper-Wiener index of bicyclic graphs. Gutman [7] obtained the relation between hyper-Wiener and Wiener index. Xu and Trinajstić [8] discussed hyper-Wiener index of graphs with cut edges. M.-H. Liu and B. L. Liu [9] determined trees with the seven smallest and fifteen greatest hyper-Wiener indices. Yu et al. [10] studied the hyper-Wiener index of trees with given parameters.All graphs considered in this paper are finite and simple. LetG be a simple graph with vertex set V
(
G
)
=
v
1
,
v
2
,
…
,
v
n and edge set E
(
G
). For a vertex v
∈
V
(
G
), the degree and the neighborhood of v are denoted by d
G
(
v
) and N
G
(
v
) (or written as d
(
v
) and N
(
v
) for short). A vertex v of degree 1 is called pendant vertex. An edge e
=
u
v incident with the pendant vertex v is called a pendant edge. For a subset U of V
(
G
), let G
-
U be the subgraph of G obtained from G by deleting the vertices of U and the edges incident with them. Similarly, for a subset E
′ of E
(
G
), we denote by G
-
E
′ the subgraph of G obtained from G by deleting the edges of E
′. If U
=
{
v
} and E
′
=
u
v, the subgraphs G
-
U and G
-
E
′ will be written as G
-
v and G
-
u
v for short, respectively. For any two nonadjacent vertices u and v in graph G, we use G
+
u
v to denote the graph obtained from G by adding a new edge u
v. Denote by S
n and P
n the star and the path on n vertices, respectively.A tree is a connected acyclic graph. LetT be a tree of order n with diameter d. If d
=
n
-
1, then T
≅
P
n; and if d
=
2, then T
≅
S
n. Therefore, in the following, we assume that 3
≤
d
≤
n
-
2
. Let T
n
,
d
=
T
:
T is a tree with order n and diameter d, 3
≤
d
≤
n
-
2
. Liu and Pan [11] characterized the minimum and second-minimum Wiener indices of trees in the set T
n
,
d
3
≤
d
≤
n
-
2, and Yu et al. [10] characterized the minimum hyper-Wiener index of all trees on n vertices with diameter d. Motivated by these articles, we will characterize the second-minimum hyper-Wiener indices of trees in the set T
n
,
d
3
≤
d
≤
n
-
2 in this paper.


## 2. Preliminaries

Lemma 1 (see [8]).
LetH, X, and Y be three connected graphs disjoint in pair. Suppose that u
,
v are two vertices of H, v
1 is a vertex of X, and u
1 is a vertex of Y. Let G be the graph obtained from H, X, and Y by identifying v with v
1 and u with u
1, respectively. Let G
1 be the graph obtained from H
,
X, and Y by identifying three vertices v
,
v
1, and u
1, and let G
2 be the graph obtained from H
,
X, and Y by identifying three vertices u
,
v
1, and u
1. Then one has (4)
W
W
G
1
<
W
W
G
o
r
W
W
G
2
<
W
W
G
.By Lemma1, we have the following result.Corollary 2.
LetG be a graph and u
,
v
∈
V
(
G
)
. Suppose that G
p
,
q
∗ is the graph obtained from G by attaching p
,
q pendant vertices to u
,
v, respectively. Then (5)
W
W
G
p
-
i
,
q
+
i
∗
<
W
W
G
p
,
q
∗
,
1
≤
i
≤
p
,or (6)
W
W
G
p
+
i
,
q
-
i
∗
<
W
W
G
p
,
q
∗
,
1
≤
i
≤
q
.LetG
1
,
G
2 be two connected graphs with V
(
G
1
)
∩
V
(
G
2
)
=
v. Let G
1
v
G
2 be a graph with V
(
G
1
)
∪
V
(
G
2
) as its vertex set and E
(
G
1
)
∪
E
(
G
2
) as its edge set. We have the following result.Lemma 3 (see [8]).
LetH be a connected graph, T
m be a tree of order m, and V
(
H
)
∩
V
(
T
m
)
=
{
v
}
. Then (7)
W
W
H
v
T
m
≥
W
W
H
v
S
m
,and equality holds if and only if H
v
T
m
≅
H
v
S
m, where v is the center of star S
m
.Lemma 4 (see [6]).
LetG be a connected graph of order n, v be a pendant vertex of G, and v
w
∈
E
(
G
). Then(1)
W
(
G
)
=
W
(
G
-
v
)
+
D
G
-
v
(
w
)
+
n
-
1;
(2)
S
(
G
)
=
S
(
G
-
v
)
+
D
D
G
-
v
(
w
)
+
2
D
G
-
v
(
w
)
+
n
-
1
.By Lemma4 and the definition of hyper-Wiener index, we have the following result.Corollary 5.
LetG be a connected graph of order n, v be a pendant vertex of G, and v
w
∈
E
(
G
). Then (8)
W
W
G
=
W
W
G
-
v
+
1
2
D
D
G
-
v
w
+
3
2
D
G
-
v
w
+
n
-
1
.Lemma 6 (see [9]).
LetG be a connected graph on n
≥
2 vertices and v be a vertex of G. Let G
k
,
l be the graph obtained from G by attaching two new paths P
:
v
v
1
v
2
⋯
v
k and Q
:
v
u
1
u
2
⋯
u
l of length k and l at v, respectively, where u
1
,
…
,
u
l and v
1
,
…
,
v
k are distinct new vertices. Let G
k
+
1
,
l
-
1
=
G
k
,
l
-
u
l
-
1
u
l
+
v
k
u
l. If k
≥
l
≥
1, then (9)
W
W
G
k
,
l
<
W
W
G
k
+
1
,
l
-
1
.Letv
1 be a vertex of graph G, and v
2
,
…
,
v
t
+
s
,
u
0 are distinct new vertices (not in G). Let G
′ be the graph G
v
1
P, where P is a new path v
1
v
2
⋯
v
t
+
s
. Let M
t
,
t
+
s
=
G
′
+
v
t
u
0 and M
t
+
i
,
t
+
s
=
G
′
+
v
t
+
i
u
0, where 1
≤
i
≤
s.Lemma 7 (see [9]).
SupposeG is a connected graph on n
≥
2 vertices or has only one vertex. If t
≥
s
≥
1, then W
W
(
M
t
,
t
+
s
)
≤
W
W
(
M
t
+
i
,
t
+
s
), where 1
≤
i
≤
s
.


## 3. Main Results

In this section, we will give the second-minimum hyper-Wiener index in the setT
n
,
d
(
3
≤
d
≤
n
-
2
). In order to formulate our results, we need to define some trees as follows.LetT
n
,
d
(
p
1
,
…
,
p
d
-
1
) be a tree of order n obtained from a path P
d
+
1
=
v
0
v
1
⋯
v
d
-
1
v
d by attaching p
i pendant vertices to v
i
,
1
≤
i
≤
d
-
1, respectively, where n
=
d
+
1
+
∑
i
=
1
d
-
1
p
i
,
p
i
≥
0
,
i
=
1,2
,
…
,
d
-
1
. Denote T
n
,
d
,
i
=
T
n
,
d
(
0
,
…
,
0
︸
i
-
1
,
n
-
d
-
1,0
,
…
,
0
) (see Figure 1(b)), and we note that T
n
,
d
,
i
≅
T
n
,
d
,
d
-
i
.Figure 1
(a)
(b)
(c)
(d)DenoteZ
n
,
d
,
i
,
j
=
T
n
,
d
(
0
,
…
,
0
︸
i
-
1
,
n
-
d
-
2
,
0
,
…
,
0
︸
j
-
i
-
1
,
1,0
,
…
,
0
) (see Figure 1(a)).For2
≤
i
≤
d
-
2, let X
n
,
d
,
i be a graph obtained from T
n
-
1
,
d
,
i by attaching a pendant vertex to one pendant vertex of T
n
-
1
,
d
,
i except for v
0
,
v
d (see Figure 1(d)). Then X
n
,
d
,
i
≅
X
n
,
d
,
d
-
i. Let Y
n
,
d
,
i be a graph obtained from T
d
+
2
,
d
,
i by attaching n
-
d
-
2 pendant vertices to one pendant vertex of T
d
+
2
,
d
,
i except for v
0
,
v
d (see Figure 1(c)). Then Y
n
,
d
,
i
≅
Y
n
,
d
,
d
-
i
.Yu et al. [10] characterized that T
n
,
d
,
d
/
2 had the minimum hyper-Wiener index of all trees on n vertices with diameter d. In the following, we firstly give possible trees with the second-minimum hyper-Wiener indices in the set T
n
,
d
(
3
≤
d
≤
n
-
2
).DenoteT
1
=
T
n
,
d
,
i
:
1
≤
i
≤
d
-
1, T
2
=
X
n
,
d
,
i
:
2
≤
i
≤
d
-
2, T
3
=
Y
n
,
d
,
i
:
2
≤
i
≤
d
-
2, and T
4
=
Z
n
,
d
,
i
,
j
:
1
≤
i
<
j
≤
d
-
1.Lemma 8.
LetT
∈
T
n
,
d. Then W
W
(
T
)
≥
W
W
(
T
n
,
d
,
i
), or W
W
(
T
)
≥
W
W
(
X
n
,
d
,
i
), or W
W
(
T
)
≥
W
W
(
Y
n
,
d
,
i
), or W
W
(
T
)
≥
W
W
(
Z
n
,
d
,
i
,
j
).Proof.
IfT
∈
T
1, the conclusion is obvious. If T
∈
T
1, let P
d
+
1
=
v
0
v
1
⋯
v
d
-
1
v
d be a path of length d in T with d
(
v
0
)
=
d
(
v
d
)
=
1
. Let V
d
=
{
v
i
:
d
(
v
i
)
≥
3
,
1
≤
i
≤
d
-
1
}
. Since n
≥
d
+
2
,
V
d
≠
∅, we consider two cases.
Case  1 (
V
d
≥
2
). By Lemma 3, (10)
W
W
T
≥
W
W
T
n
,
d
p
1
,
…
,
p
d
-
1
.
By Corollary2, W
W
(
T
n
,
d
(
p
1
,
…
,
p
d
-
1
)
)
≥
W
W
(
T
n
,
d
(
0
,
…
,
0
︸
i
-
1
,
q
i
,
0
,
…
,
0
︸
j
-
i
-
1
,
q
j
,
0
,
…
,
0
)
)
≥
W
W
(
Z
n
,
d
,
i
,
j
), where p
1
+
⋯
+
p
d
-
1
=
q
i
+
q
j
.
So(11)
W
W
T
≥
W
W
Z
n
,
d
,
i
,
j
.
Case  2 (
V
d
=
1
). Let v
i
∈
V
d and N
v
i
∖
v
i
-
1
,
v
i
+
1
=
{
w
1
,
w
2
,
…
,
w
s
} with d
(
w
j
)
≥
2
,
1
≤
j
≤
r, and d
(
w
r
+
1
)
=
⋯
=
d
(
w
s
)
=
1
. Then r
≥
1 as T
∉
T
1
. Let T
i
(
w
j
) be subtrees of T
-
v
i which contain w
j, and V
T
i
w
j
=
s
j
+
1
,
1
≤
j
≤
r
. By Lemma 3, we can obtain a tree T
1 obtained from T
d
+
s
+
1
,
d
,
i by attaching s
j pendant vertices to w
j
,
1
≤
j
≤
s, respectively, such that W
W
(
T
)
>
W
W
(
T
1
). By Corollary 2, we can obtain a tree T
2
∈
T
2
∪
T
3 such that W
W
(
T
1
)
≥
W
W
(
T
2
)
. So W
W
(
T
)
≥
W
W
(
X
n
,
d
,
i
), or W
W
(
T
)
≥
W
W
(
Y
n
,
d
,
i
).Lemma 9.
LetP
=
v
0
v
1
⋯
v
d be a path of order d
+
1. Then (12)
D
P
v
j
=
2
j
2
-
2
d
j
+
d
2
+
d
2
,
D
D
P
v
j
=
6
j
2
+
6
d
j
2
-
6
d
2
j
-
6
d
j
+
2
d
3
+
3
d
2
+
d
6
,for 1
≤
j
≤
d
-
1
. Moreover, if 1
≤
i
<
j
≤
d
/
2
,
D
P
(
v
i
)
>
D
P
(
v
j
), and D
D
P
(
v
i
)
>
D
D
P
(
v
j
); if d
/
2
≤
i
<
j
≤
(
d
-
1
)
,
D
P
(
v
i
)
<
D
P
(
v
j
), and D
D
P
(
v
i
)
<
D
D
P
(
v
j
)
.Proof.
By the definition ofD
G
(
v
) and D
D
G
(
v
), we have (13)
D
P
v
j
=
1
+
2
+
⋯
+
j
+
1
+
2
+
⋯
+
d
-
j
=
2
j
2
-
2
d
j
+
d
2
+
d
2
,
D
D
P
v
j
=
1
2
+
2
2
+
⋯
+
j
2
+
1
2
+
2
2
+
⋯
+
d
-
j
2
=
6
j
2
+
6
d
j
2
-
6
d
2
j
-
6
d
j
+
2
d
3
+
3
d
2
+
d
6
.Then D
P
(
v
i
)
-
D
P
(
v
j
)
=
(
i
-
j
)
(
i
+
j
-
d
)
,
D
D
P
(
v
i
)
-
D
D
P
(
v
j
)
=
(
d
+
1
)
(
i
-
j
)
(
i
+
j
-
d
), and thus the results hold.Lemma 10.
(1) For anyT
∈
T
1
,
W
W
(
T
)
≥
W
W
T
n
,
d
,
d
/
2, with equality if and only if T
≅
T
n
,
d
,
d
/
2
.
(2) For anyT
∈
T
2
,
W
W
(
T
)
≥
W
W
X
n
,
d
,
d
/
2, with equality if and only if T
≅
X
n
,
d
,
d
/
2
.
(3) For anyT
∈
T
3
,
W
W
(
T
)
≥
W
W
Y
n
,
d
,
d
/
2, with equality if and only if T
≅
Y
n
,
d
,
d
/
2
.
(4) For anyT
∈
T
4
,
W
W
(
T
)
≥
W
W
Z
n
,
d
,
d
/
2
,
d
/
2
+
1, with equality if and only if T
≅
Z
n
,
d
,
⌊
d
/
2
⌋
,
d
/
2
+
1
.Proof.
Letv
=
v
i and two paths P
=
v
0
v
1
⋯
v
i
,
Q
=
v
i
v
i
+
1
⋯
v
d in Lemma 6. We obtain the results of (1), (2), and (3). In the following, we prove (4).
LetT
=
Z
n
,
d
,
i
,
j be a tree which W
W
(
T
) is as small as possible in the set T
4. Let P
=
v
0
v
1
⋯
v
d
-
1
v
d be a path of length d in T with d
v
0
=
d
v
d
=
1, and  v
d
+
1 be a pendant vertex of T which is adjacent to v
j. By Lemma 7 and the choice of T, we know that j
=
i
+
1
. Note that Z
n
,
d
,
i
,
i
+
1
-
v
0
≅
Z
n
,
d
,
i
-
1
,
i
-
v
d, and then by Corollary 5, we have (14)
W
W
Z
n
,
d
,
i
,
i
+
1
-
W
W
Z
n
,
d
,
i
-
1
,
i
=
3
2
n
-
d
-
2
2
i
-
d
-
1
+
2
i
-
d
+
1
+
1
2
n
-
d
-
2
2
i
-
d
-
1
d
+
1
+
d
+
1
2
i
-
d
+
1
=
1
2
d
+
4
n
-
d
-
2
2
i
-
d
-
1
+
2
i
-
d
+
1
.
Thus, ifi
>
d
/
2, W
W
(
Z
n
,
d
,
i
,
i
+
1
)
-
W
W
(
Z
n
,
d
,
i
-
1
,
i
)
>
0; if i
≤
d
/
2, W
W
(
Z
n
,
d
,
i
,
i
+
1
)
-
W
W
(
Z
n
,
d
,
i
-
1
,
i
)
≤
0, with equality if and only if d
=
2
i
=
n
-
3 or d
=
2
i
+
1
=
n
-
2. So, for any T
∈
T
4
,
W
W
(
T
)
≥
W
W
Z
n
,
d
,
d
/
2
,
d
/
2
+
1, with equality if and only if T
≅
Z
n
,
d
,
d
/
2
,
d
/
2
+
1
.Lemma 11.
Let3
≤
d
≤
n
-
3, and then(1)
W
W
Z
n
,
d
,
d
/
2
,
d
/
2
+
1
<
W
W
X
n
,
d
,
d
/
2
≤
W
W
Y
n
,
d
,
d
/
2;
(2)
W
W
Z
n
,
d
,
d
/
2
,
d
/
2
+
1
<
W
W
T
n
,
d
,
d
/
2
-
1
.Proof.
(1) We denoteZ
≕
Z
n
,
d
,
d
/
2
,
d
/
2
+
1, X
≕
X
n
,
d
,
d
/
2
,
Y
≕
Y
n
,
d
,
⌊
d
/
2
⌋.
Note thatZ
n
,
d
,
d
/
2
,
d
/
2
+
1
-
v
d
+
1
≅
X
n
,
d
,
d
/
2
-
v
d
+
2, and then by Corollary 5, we have (15)
W
W
Z
n
,
d
,
d
/
2
,
d
/
2
+
1
-
W
W
X
n
,
d
,
d
/
2
=
3
2
D
Z
-
v
d
+
1
v
d
/
2
+
1
-
D
X
-
v
d
+
2
v
d
+
1
+
1
2
D
D
Z
-
v
d
+
1
v
d
/
2
+
1
-
D
D
X
-
v
d
+
2
v
d
+
1
=
3
2
2
-
2
d
+
2
d
2
+
1
2
4
-
2
d
-
d
2
2
-
2
d
-
d
2
=
5
-
4
d
+
4
d
2
-
d
-
d
2
2
≤
5
-
4
d
+
4
d
2
≤
5
-
2
d
<
0
.
Namely,(16)
W
W
Z
n
,
d
,
d
/
2
,
d
/
2
+
1
<
W
W
X
n
,
d
,
d
/
2
.
Note thatX
d
+
3
,
d
,
d
/
2
≅
Y
d
+
3
,
d
,
d
/
2, and then by Lemma 4, we have (17)
W
W
X
n
,
d
,
d
/
2
-
W
W
Y
n
,
d
,
d
/
2
=
1
2
W
X
n
,
d
,
d
/
2
-
W
Y
n
,
d
,
d
/
2
+
1
2
S
X
n
,
d
,
d
/
2
-
S
Y
n
,
d
,
d
/
2
=
1
2
W
X
-
v
d
+
3
-
W
Y
-
v
d
+
3
+
D
X
-
v
d
+
3
v
d
/
2
-
D
Y
-
v
d
+
3
v
d
+
1
+
1
2
S
X
-
v
d
+
3
-
S
Y
-
v
d
+
3
+
D
D
X
-
v
d
+
3
v
d
/
2
-
D
D
Y
-
v
d
+
3
v
d
+
1
+
2
D
X
-
v
d
+
3
v
d
/
2
-
D
Y
-
v
d
+
3
v
d
+
1
=
1
2
W
X
n
-
1
,
d
,
d
/
2
-
W
Y
n
-
1
,
d
,
d
/
2
-
d
+
1
+
1
2
S
X
n
-
1
,
d
,
d
/
2
-
S
Y
n
-
1
,
d
,
d
/
2
+
5
-
d
2
+
1
2
-
d
-
d
2
+
1
2
+
2
-
d
+
1
<
1
2
W
X
n
-
1
,
d
,
d
/
2
-
W
Y
n
-
1
,
d
,
d
/
2
-
d
+
1
+
1
2
S
X
n
-
1
,
d
,
d
/
2
-
S
Y
n
-
1
,
d
,
d
/
2
-
2
d
+
7
<
W
W
X
n
-
1
,
d
,
d
/
2
-
W
W
Y
n
-
1
,
d
,
d
/
2
<
⋯
<
W
W
X
d
+
3
,
d
,
d
/
2
-
W
W
Y
d
+
3
,
d
,
d
/
2
=
0
.
Namely,(18)
W
W
X
n
,
d
,
d
/
2
≤
W
W
Y
n
,
d
,
d
/
2
.
(2) By Lemma9, D
P
d
+
1
v
d
/
2
+
1
≤
D
P
d
+
1
v
d
/
2
-
1, and D
D
P
d
+
1
v
d
/
2
+
1
≤
D
D
P
d
+
1
v
d
/
2
-
1
.By Corollary 5 and Lemma 9, (19)
W
W
Z
n
,
d
,
d
/
2
,
d
/
2
+
1
-
W
W
T
n
,
d
,
d
/
2
-
1
=
W
W
T
n
-
1
,
d
,
d
/
2
-
W
W
T
n
-
1
,
d
,
d
/
2
-
1
+
3
2
D
P
d
+
1
v
d
/
2
+
1
-
3
2
D
P
d
+
1
v
d
/
2
-
1
+
1
2
D
D
P
d
+
1
v
d
/
2
+
1
-
1
2
D
D
P
d
+
1
v
d
/
2
-
1
+
3
n
-
d
-
2
≤
W
W
T
n
-
1
,
d
,
d
/
2
-
W
W
T
n
-
1
,
d
,
d
/
2
-
1
+
3
n
-
d
-
2
=
1
2
D
D
T
n
-
2
,
d
-
1
,
d
/
2
-
1
v
1
-
D
D
T
n
-
2
,
d
-
1
,
d
/
2
-
1
v
d
-
1
+
3
D
T
n
-
2
,
d
-
1
,
d
/
2
-
1
v
1
-
3
D
T
n
-
2
,
d
-
1
,
d
/
2
-
1
v
d
-
1
+
3
n
-
d
-
2
=
1
2
d
2
2
-
d
-
d
2
+
1
2
+
3
d
2
-
d
-
d
2
+
1
n
-
d
-
2
+
3
n
-
d
-
2
=
1
2
-
d
2
-
5
d
+
2
+
8
d
2
+
2
d
d
2
n
-
d
-
2
≤
1
2
-
d
2
-
5
d
+
2
+
4
d
+
d
2
n
-
d
-
2
=
1
2
-
d
+
2
n
-
d
-
2
<
0
.
Namely,(20)
W
W
Z
n
,
d
,
d
/
2
,
d
/
2
+
1
<
W
W
T
n
,
d
,
d
/
2
-
1
.Theorem 12.
LetT
∈
T
n
,
d
∖
T
n
,
d
,
d
/
2
. Then (21)
W
W
T
≥
W
W
Z
n
,
d
,
d
/
2
,
d
/
2
+
1
,with equality if and only if T
≅
Z
n
,
d
,
⌊
d
/
2
⌋
,
⌊
d
/
2
⌋
+
1
.Proof.
Ifd
=
n
-
2, note that T
n
,
n
-
2 contains no other trees than T
n
,
d
,
⌊
d
/
2
⌋
,
T
n
,
d
,
⌊
d
/
2
⌋
-
1
,
…
,
T
n
,
d
,
2
,
T
n
,
d
,
1, and by Lemma 6, take v
=
v
j and two paths P
=
v
0
v
1
⋯
v
j
,
Q
=
v
j
v
j
+
1
⋯
v
d, and we have W
W
(
T
n
,
d
,
⌊
d
/
2
⌋
)
<
W
W
(
T
n
,
d
,
⌊
d
/
2
⌋
-
1
)
<
⋯
<
W
W
(
T
n
,
d
,
2
)
<
W
W
(
T
n
,
d
,
1
)
.
So,(22)
W
W
T
≥
W
W
T
n
,
d
,
d
/
2
-
1
,with equality if and only if T
≅
T
n
,
d
,
⌊
d
/
2
⌋
-
1
≅
Z
n
,
d
,
⌊
d
/
2
⌋
,
⌊
d
/
2
⌋
+
1
.
If3
≤
d
≤
n
-
3, by Lemmas 8, 10, and 11, we have (23)
W
W
T
≥
W
W
Z
n
,
d
,
d
/
2
,
d
/
2
+
1
,with equality if and only if T
≅
Z
n
,
d
,
⌊
d
/
2
⌋
,
⌊
d
/
2
⌋
+
1
.



---

*Source: 7241349-2016-09-22.xml*