# Spanning 3-Ended Trees in Almost Claw-Free Graphs

Authors: Xiaodong Chen; Meijin Xu; Yanjun Liu
Journal: Discrete Dynamics in Nature and Society
 (2015)

---

## Abstract

We prove that ifG is a k-connected (k
≥
2) almost claw-free graph of order n and σ
k
+
3
(
G
)
≥
n
+
2
k
-
2, then G contains a spanning 3-ended tree, where σ
k
(
G
)
=
min
⁡
{
∑
v
∈
S
‍
deg
⁡
(
v
)
:
S is an independent set of G with S
=
k
}.


---

## Body

## 1. Introduction

In this paper, only finite and simple graphs are considered. We refer to [1] for notation and terminology not defined here. If B
⊆
V
(
G
), as well as every edge of G incident with the vertices in B, then B is adominating set. We use γ
(
G
) to denote thedomination number of a graph G, where γ
(
G
)
=
min
⁡
{
S
:
S
is a dominating set of
G
}. If a graph G has no K
1,3 subgraph, then G isclaw-free. The vertex of degree 3 in K
1,3 is calledclaw center of a claw. Let N
(
v
)
=
{
u
:
u
v
∈
E
(
G
)
} and N
[
v
]
=
N
(
v
)
∪
{
v
}. If, for any vertex v
∈
V
(
G
), γ
(
N
(
v
)
)
≤
2 and the set of all claw centers in K
1,3 subgraphs of G is an independent set, then G isalmost claw-free. A claw-free graph is almost claw-free.N
H
(
S
)
=
{
v
:
v
∈
V
(
H
) and u
v
∈
E
(
G
) for some vertex u
∈
V
(
S
)
}, and d
H
(
S
)
=
N
H
S. We use σ
k
(
G
) to denote the minimum degree sum of all the independent sets with order k in G. a
P
b or P
[
a
,
b
] denotes a path with a positive orientation from x to y with end vertices a, b. For a path P
[
a
,
b
], x
,
y
∈
V
(
P
), let x
P
y denote the subpath with end vertices x, y with positive orientation and y
P
-
x denote the subpath with end vertices y, x with negative orientation. Let w
(
G
) denote the number of components of a graph G.As we know, graph theory focuses on graphs composed by vertices and edges. The vertices in a graph are considered as discrete points which is usually discussed in control problems. Then there are a lot of results using graph theory to solve control problems [2–8].A spanning tree in a graphG with no more than k leaves is called a spanning k-ended tree of G. There are many results about the properties of spanning trees [9–13]. Kyaw [14, 15] gave some degree sum conditions for K
1,4-free graphs to contain spanning k-ended trees.Theorem 1 (see [14]).
IfG is a connected K
1,4-free graph and σ
4
(
G
)
≥
G
-
1, then G contains spanning 3-ended trees.Theorem 2 (see [15]).
IfG is a connected K
1,4-free graph, then the following properties hold:(i)
G contains a hamiltonian path if σ
3
(
G
)
≥
G.
(ii)
G contains spanning k-ended trees if σ
k
+
1
(
G
)
≥
G
-
k
/
2 for an integer k
≥
3.On the other hand, Kano et al. [16] obtained sharp sufficient conditions for claw-free graphs to contain spanning k-ended trees.Theorem 3 (see [16]).
IfG is a connected claw-free graph of order n and σ
k
+
1
(
G
)
≥
n
-
k (k
≥
2), then G contains spanning k-ended trees with the maximum degree at most 3.Recently, Chen et al. [17] gave some degree sum conditions for k-connected K
1,4-free graphs to contain spanning 3-ended trees.Theorem 4 (see [17]).
IfG is a k-connected K
1,4-free graph of order n and σ
k
+
3
(
G
)
≥
n
+
2
k
-
2 (k
≥
2), then G contains spanning 3-ended trees.Inspired by Theorems4 and 5, in this paper, we further explore sufficient conditions for k-connected almost claw-free graphs to contain spanning 3-ended trees which holds for claw-free graphs.Theorem 5.
IfG is a k-connected almost claw-free graph of order n and σ
k
+
3
(
G
)
≥
n
+
2
k
-
2 (k
≥
2), then G contains spanning 3-ended trees.Obviously, there are a lot of almost claw-free graphs containingK
1,4 subgraphs, so to some extent Theorem 5 is a generalization of Theorem 4.


## 2. Preliminaries

We need the following result given by Ryjáček [18] to prove Theorem 5.Lemma 6 (see [18]).
γ
(
N
(
v
)
)
=
2 for any claw center v in an almost claw-free graph.We mainly use the definition and properties of insertible vertex defined in [16] to prove Theorem 5.Suppose thatG is a connected nonhamiltonian graph and C is longest cycle in G with counterclockwise direction as positive orientation. Assume that R is a component of G
-
C and N
C
(
R
)
=
{
u
1
,
u
2
,
…
,
u
m
} such that u
1
,
u
2
,
…
,
u
m are labeled in order along the positive direction of C
. Let S
j
=
C
(
u
j
,
u
j
+
1
], 1
≤
j
≤
m
-
1, and S
m
=
C
(
u
m
,
u
1
]. A vertex u in S
j is an insertible vertex if u has two consecutive neighbors v and v
+ in C
-
S
j.Chen and Schelp [19] proposed the following two results.Lemma 7 (see [19]).
For eachS
j
,
S
j
-
{
v
j
+
1
} contains a noninsertible vertex.Assume thatv
j is the first noninsertible vertex in S
j
-
{
u
j
+
1
} for each j
∈
[
1
,
m
].Lemma 8 (see [19]).
Letx
i
∈
C
[
u
i
+
,
v
i
], x
j
∈
C
[
u
j
+
,
v
j
] with 1
≤
i
<
j
≤
m. Then(a)
there is no pathP
[
x
i
,
x
j
] in G such that P
[
x
i
,
x
j
]
∩
V
(
C
)
=
{
x
i
,
x
j
},
(b)
for any vertexu in C
[
x
i
+
,
x
j
-
], if u
x
i
∈
E
(
G
), then u
-
x
j
∉
E
(
G
). By symmetry, for any vertex u in C
[
x
j
+
,
x
i
-
], if u
x
j
∈
E
(
G
), then u
-
x
i
∉
E
(
G
),
(c)
for any vertexu in C
[
x
i
,
x
j
], if u
x
i
,
u
x
j
∈
E
(
G
), then u
-
u
+
∉
E
(
G
). By symmetry, for any vertex u in C
[
x
j
,
x
i
], if u
x
i
,
u
x
j
∈
E
(
G
), then u
-
u
+
∉
E
(
G
).Suppose, for somei
∈
[
1
,
m
], N
(
v
i
)
∩
V
(
G
-
C
-
R
)
≠
∅ and v
i
′ is the second noninsertible vertex in S
i
-
{
u
i
+
1
}. Then Chen et al. [17] gave the following result.Lemma 9 (see [17]).
Let1
≤
i
<
j
≤
m, x
i
∈
C
[
v
i
+
,
v
i
′
] and x
j
∈
C
[
u
j
+
,
v
j
]. Then the following properties hold:(a)
There does not exist a pathP
[
x
i
,
x
j
] in G such that P
[
x
i
,
x
j
]
∩
V
(
C
)
=
{
x
i
,
x
j
}.
(b)
For every vertexu
∈
C
[
x
i
+
,
x
j
-
], if u
x
i
∈
E
(
G
), then u
-
x
j
∉
E
(
G
); similarly, for every u
∈
C
[
x
j
+
,
x
i
-
], if u
x
j
∈
E
(
G
), then u
-
x
i
∉
E
(
G
).
(c)
For every vertexu
∈
C
[
x
i
,
x
j
], if u
x
i
,
u
x
j
∈
E
(
G
), then u
-
u
+
∉
E
(
G
); by symmetry, for any vertex u in C
[
x
j
,
x
i
], if u
x
i
,
u
x
j
∈
E
(
G
), then u
-
u
+
∉
E
(
G
).


## 3. Proof of Theorem5

To the contrary, suppose thatG satisfies the conditions of Theorem 5 and any spanning tree in G contains more than 3 leaves. Let P
=
P
[
x
,
y
] be longest path in G such that P satisfies the following two conditions:(T1)
w
(
G
-
P
) is minimum.
(T2)
|
P
[
x
,
u
1
]
| is minimum such that u
1 is the first vertex in P with N
(
u
1
)
∩
V
(
G
-
P
)
≠
∅, subject to (T1).Suppose thatR is a component in G
-
P, and {
u
1
,
…
,
u
m
}
=
N
P
(
R
) with u
1
,
…
,
u
m in order along the positive direction of P. Let R
I denote an independent set in R.LetG
′ denote a graph with V
(
G
′
)
=
V
(
G
)
∪
{
u
0
}, E
(
G
′
)
=
E
(
G
)
∪
{
u
0
u
:
u
∈
V
(
G
)
}. Then C
=
u
0
P
[
x
,
y
]
u
0 is a maximal cycle in G
′. We define the counterclockwise orientation as the positive direction of C. Let S
i denote the segment C
(
u
i
,
u
i
+
1
] for 0
≤
i
≤
m
-
1, and S
m
=
C
(
u
m
,
u
0
]. By Lemma 7, let v
i denote the first noninsertible vertex in S
i, for i
∈
[
0
,
m
], and U
=
{
v
0
,
v
1
,
…
,
v
m
}. By Lemma 8(a), U is an independent set.C can be divided into disjoint intervals S
=
C
[
a
,
b
] with a
,
b
+
∉
N
(
U
) and C
[
a
+
,
b
]
⊆
N
(
U
). We call the intervals U
-segments. If a
=
b, then C
a
+
,
b
=
∅; that is, if S
=
1, then d
U
(
S
)
=
0. By the definition of U-segment, for any U-segment S, there exists l
∈
[
0
,
m
] such that S
⊆
C
[
v
l
,
v
l
+
1
-
] (subscripts expressed modulo m
+
1).Claim 1.
x
=
v
0 and y
∉
N
(
v
i
) for any i
∈
[
0
,
m
-
1
].Proof.
Suppose thatx is an insertible vertex such that x
u
,
x
u
+
∈
E
(
G
), where u
,
u
+
∈
C
-
S
0. If u
≠
y, then we can get a path P
′
=
P
[
x
+
,
u
]
x
P
[
u
+
,
y
], a contradiction to (T2). If u
=
y, then let P
′
=
P
[
x
+
,
y
]
x, a contradiction to (T2). Thus x
=
v
0. Suppose v
i
y
∈
E
(
G
), for some i
∈
[
0
,
m
-
1
]. Obviously, u
0
=
y
+. Since y
v
i
,
y
+
v
i
∈
E
(
G
) and y
∈
C
-
S
i
,
v
i is an insertible vertex, a contradiction.Claim 2.
For any vertexu
∈
V
(
P
), if N
[
u
] is claw-free, then d
U
(
u
)
≤
1.Proof.
Suppose thatu is in some U-segment S with S
⊆
C
[
v
i
,
v
i
+
1
-
], i
∈
[
0
,
m
], and v
i
1
,
v
i
2
∈
N
U
(
u
) with 0
≤
i
1
<
i
2
≤
m. Then by Lemma 8(c), u
-
u
+
∉
E
(
G
). Since G
[
u
,
u
-
,
u
+
,
v
i
1
]
≠
K
1,3, v
i
1
u
-
∈
E
(
G
) or v
i
1
u
+
∈
E
(
G
). Similarly, v
i
2
u
-
∈
E
(
G
) or v
i
2
u
+
∈
E
(
G
). Obviously, at least one vertex in {
v
i
1
,
v
i
2
} is not in C
[
v
i
,
v
i
+
1
-
]. Without loss of generality, suppose v
i
1
∉
C
[
v
i
,
v
i
+
1
-
] and v
i
1
u
-
∈
E
(
G
). Then by v
i
1
u
-
,
v
i
1
u
∈
E
(
G
)
,
v
i
1 is an insertible vertex, a contradiction.Claim 3.
d
U
(
u
)
≤
2 for any vertex u
∈
V
(
P
), and if d
U
(
u
)
=
2, then u is a claw center.Proof.
Without loss of generality, suppose thatu is in U-segment S and S
⊆
C
[
v
0
,
v
1
-
]. If S
=
1, then d
U
(
u
)
=
0. Suppose S
≥
2 and S
=
{
x
0
,
x
1
,
x
2
,
…
,
x
h
}, where x
0
,
x
1
,
x
2
,
…
,
x
h are in order along the positive direction of C
. Then x
0
∉
N
(
U
), x
i
∈
N
(
U
) for i
∈
[
1
,
h
]. For some i
∈
[
1
,
h
], suppose v
i
1
,
v
i
2
,
v
i
3
∈
N
U
(
x
i
) with 0
≤
i
1
<
i
2
<
i
3
≤
m. Then x
i is a claw center. By Lemma 6, suppose y
1, y
2 are two distinct domination vertices of N
(
x
i
). Then N
[
y
1
], N
[
y
2
] are claw-free and at least two vertices in {
v
i
1
,
v
i
2
,
v
i
3
} are incident with y
1 or y
2. Without loss of generality, suppose v
i
1
y
1
,
v
i
2
y
1
∈
E
(
G
). Then y
1
∈
V
(
P
), and y
1
-
y
1
+
∉
E
(
G
) by Lemma 8(c). Suppose S
j
=
C
(
u
j
,
u
j
+
1
] containing y
1, 0
≤
j
≤
m. Obviously, at least one vertex in {
v
i
1
,
v
i
2
} is not in S
j. Without loss of generality, suppose v
i
1
∉
S
j. Since v
i
1 is a noninsertible vertex and v
i
1
y
1
∈
E
(
G
), y
1
-
v
i
1
,
y
1
+
v
i
1
∉
E
(
G
). Thus G
[
y
1
,
y
1
-
,
y
1
+
,
v
i
1
]
=
K
1,3, a contradiction. If d
U
(
u
)
=
2, then by Claim 2, u is a claw center.Claim 4.
For anyU-segment S not containing y, S contains at most one vertex u with d
U
(
u
)
=
2, and d
U
(
S
)
≤
S.Proof.
Ify
∉
N
(
U
), then there exists a U-segment S with S
=
{
y
,
u
0
}. Suppose y
∈
N
(
U
) and y in U-segment S, then u
0
∈
S by u
0
=
y
+ and u
0
∈
N
(
U
). Thus if y
∉
S, then u
0
∉
S
0. Without loss of generality, suppose S
=
{
x
0
,
x
1
,
x
2
,
…
,
x
h
}
⊆
C
[
v
i
,
v
i
+
1
-
], 0
≤
i
≤
m, where x
0
,
x
1
,
x
2
,
…
,
x
h are in order along the positive direction of C. By Claim 3, suppose that x
j is the first vertex in S with d
U
(
x
j
)
=
2, 1
≤
j
≤
h, and {
v
i
1
,
v
i
2
}
=
N
U
(
x
j
), where 0
≤
i
1
<
i
2
≤
m. Then v
i
2
≠
v
i, and, by Claim 3, x
j is a claw center. Then N
[
x
j
+
] is claw-free, and, by Claim 2, d
U
(
x
j
+
)
≤
1. Thus if j
≤
h
≤
j
+
1, then we are done.
Supposeh
>
j
+
1 and N
U
(
x
j
+
1
)
=
{
v
i
3
}, i
3
∈
[
0
,
m
]. Since G
[
x
j
+
1
,
x
j
+
2
,
x
j
,
v
i
3
]
≠
K
1,3
,
E
(
G
) contains at least one edge in {
x
j
v
i
3
,
x
j
+
2
v
i
3
,
x
j
x
j
+
2
}. Since v
i
3 is a noninsertible vertex and v
i
3
x
j
+
1
∈
E
(
G
), v
i
3
=
v
i if x
j
v
i
3 or x
j
+
2
v
i
3
∈
E
(
G
), a contradiction to Lemma 8(b) since x
j
v
i
1
,
x
j
v
i
2
∈
E
(
G
). Thus v
i
3
≠
v
i, and x
j
x
j
+
2
∈
E
(
G
). Since x
j is a claw center, N
[
x
j
+
2
] is claw-free and, by Claim 2, d
U
(
x
j
+
2
)
≤
1. Thus if h
=
j
+
2, then we are done.
Supposeh
>
j
+
2 and {
v
i
4
}
=
N
U
(
x
j
+
2
), i
4
∈
[
0
,
m
]. Since x
j
+
1
v
i
3
,
x
j
+
2
v
i
4
∈
E
(
G
) and v
i
3
≠
v
i, by Lemma 8(b) v
i
4
≠
v
i. Then v
i
4
x
j
+
3
∉
E
(
G
). Since G
[
x
j
+
2
,
x
j
,
x
j
+
3
,
v
i
4
]
≠
K
1,3
,
v
i
4
x
j or x
j
x
j
+
3
∈
E
(
G
). If v
i
4
x
j
∈
E
(
G
), then v
i
4
∈
{
v
i
1
,
v
i
2
}. Then, by Lemma 8(b), v
i
3
=
v
i
4 and v
i
4
=
v
i
2 since x
j
+
1
v
i
3
,
x
j
+
2
v
i
4
∈
E
(
G
). Then v
i
2
x
j
+
1
,
v
i
2
x
j
+
2
∈
E
(
G
), a contradiction to the noninsertablity of v
i
2. Thus x
j
x
j
+
3
∈
E
(
G
), and then N
[
x
j
+
3
] is claw-free. By Claim 2, d
U
(
x
j
+
3
)
≤
1
. Thus if h
=
j
+
3, then we are done. If h
>
j
+
3, then, proceeding in the above manners to the set L
=
{
x
j
+
4
,
…
,
x
h
}, we can get that N
[
u
] is claw-free for any vertex u in L, and then, by Claim 2, d
U
(
u
)
≤
1. It follows that S has exactly one vertex x
j with d
U
(
x
j
)
=
2 for j
∈
[
1
,
h
]. Thus the claim holds.Claim 5.
Suppose that theU-segment S
0 contains y. Then d
U
(
u
)
≤
1 for any vertex u
∈
S
0
-
{
u
0
}.Proof.
Ify
∉
N
(
U
), then S
0
=
{
y
,
u
0
} and d
U
(
y
)
=
0. Suppose y
∈
N
(
U
). Then, by Claim 1, N
U
(
y
)
=
{
v
t
}. By Lemma 8(b), N
U
(
u
)
⊆
{
v
t
} and then d
U
(
u
)
≤
1 for any vertex u
∈
S
0
-
{
u
0
}.Claim 6.
For any vertexu
i
(
1
≤
i
≤
m
) in N
P
(
R
)
=
{
u
1
,
…
,
u
m
}, d
R
I
(
u
i
)
≤
2.Proof.
Supposez
1
,
z
2
,
z
3
∈
N
R
I
(
u
i
), where z
1
,
z
2
,
z
3 are distinct vertices, i
∈
[
1
,
m
]. Since G
[
u
i
,
z
1
,
z
2
,
z
3
]
=
K
1,3
,
u
i is a claw center. By Lemma 6, suppose y
1, y
2 are the two distinct domination vertices in N
(
u
i
). Then u
i
-
,
u
i
+
∈
N
(
y
1
)
∪
N
(
y
2
), and N
[
y
1
], N
[
y
2
] are claw-free. Since u
i
-
,
u
i
+
∉
N
P
(
R
), {
y
1
,
y
2
}
∩
V
(
C
)
≠
∅. Suppose y
1, y
2 are both in V
(
C
). Then at least two vertices of z
1
,
z
2
,
z
3 are adjacent to y
1 or y
2. Without loss of generality, suppose z
1
,
z
2
∈
N
(
y
1
), and then G
[
y
1
,
z
1
,
z
2
,
y
1
+
]
=
K
1,3, a contradiction. Thus one vertex of y
1, y
2 is in V
(
C
), and the other vertex is in V
(
R
). Without loss of generality, suppose y
1
∈
V
(
C
), y
2
∈
V
(
R
). Then u
i
+
y
1
∈
E
(
G
). If z
1
,
z
2
,
z
3
∈
N
(
y
2
), then G
[
y
2
,
z
1
,
z
2
,
z
3
]
=
K
1,3, a contradiction, and, by the preceding proof, there is exactly one vertex of z
1
,
z
2
,
z
3 adjacent to y
1. Thus y
1
∈
N
P
(
R
)
-
{
u
i
}. Without loss of generality, suppose z
1
∈
N
(
y
1
). Since G
[
y
1
,
y
1
-
,
y
1
+
,
z
1
]
≠
K
1,3, y
1
-
y
1
+
∈
E
(
G
). Then we can get a longer cycle C
′
=
y
1
z
1
C
-
[
u
i
,
y
1
+
]
C
-
[
y
1
-
,
u
i
+
]
y
1 than C, a contradiction.Claim 7.
For any vertexu
i
(
1
≤
i
≤
m
) in N
P
(
R
)
=
{
u
1
,
…
,
u
m
}, if d
U
(
u
i
)
=
1 and d
R
I
(
u
i
)
=
2, then d
U
(
u
)
≤
1 and d
U
(
S
)
=
S
-
1, for any vertex u
∈
S, where S is the U-segment containing u
i.Proof.
Supposed
U
(
u
i
)
=
1 and N
R
I
(
u
i
)
=
{
z
1
,
z
2
}, i
∈
[
1
,
m
]. Since G
[
u
i
,
u
i
-
,
z
1
,
z
2
]
=
K
1,3
,
u
i is a claw center. Assume S
=
{
x
1
,
x
2
,
…
,
x
h
} and x
j
=
u
i, 2
≤
j
≤
h. If h
>
j, then, by Lemma 8(a), N
U
(
u
)
=
{
v
i
} for any vertex u
∈
{
x
j
+
1
,
…
,
x
h
}. Thus if u
∈
S with d
U
(
u
)
=
2, then u
∈
{
x
2
,
x
3
,
…
,
x
j
-
1
}. Suppose d
U
(
x
p
)
=
2, p
∈
[
2
,
j
-
1
]. By the proof of Claim 4, N
[
u
] is claw-free for any vertex u in {
x
p
+
1
,
…
,
x
h
}, which contradicts that x
j is a claw center. It follows that d
U
(
S
)
=
|
S
|
-
1.Claim 8.
For any vertexu
i
(
1
≤
i
≤
m
) in N
P
(
R
)
=
{
u
1
,
…
,
u
m
}, if d
U
(
u
i
)
=
2, then d
R
I
(
u
i
)
≤
1.Proof.
Without loss of generality, we consideru
2
. Suppose {
v
i
,
v
j
}
=
N
U
(
u
2
) with 0
≤
i
<
j
≤
m and z
1
,
z
2
∈
N
R
I
(
u
2
), where z
1, z
2 are two distinct vertices. By Claim 3, u
2 is a claw center. By Lemma 6, suppose y
1, y
2 are the two distinct domination vertices in N
(
u
2
). Then N
[
y
1
], N
[
y
2
] are claw-free and v
i
,
v
j
∈
N
(
y
1
)
∪
N
(
y
2
). Thus {
y
1
,
y
2
}
∩
V
(
C
)
≠
∅. Without loss of generality, suppose y
1
∈
V
(
C
). If y
2
∈
V
(
R
), then v
i
y
1
,
v
j
y
1
∈
E
(
G
), a contradiction to Claim 2. Suppose y
2
∈
V
(
C
). By Claim 2, v
i, v
j can not both be incident with y
1 or y
2. Without loss of generality, suppose z
1
y
1
,
z
2
y
2
,
v
i
y
1
,
v
j
y
2
∈
E
(
G
). Obviously, y
1
∈
N
P
(
R
)
-
{
u
2
}. Suppose y
1
=
u
j, j
∈
{
1,3
,
…
,
m
}. If v
i
≠
v
j
-
1, then G
[
y
1
,
y
1
+
,
v
i
,
z
1
]
=
K
1,3, a contradiction. Suppose v
i
=
v
j
-
1. Then, by G
[
y
1
,
y
1
+
,
v
i
,
z
1
]
≠
K
1,3, y
1
+
v
i
∈
E
(
G
). Obviously, all the vertices in C
(
u
j
-
1
,
v
j
-
1
-
) can be inserted into C
[
y
1
,
u
j
-
1
]. Let y
1
P
1
u
j
-
1 denote the path by the above inserting process with V
(
P
1
)
=
V
(
C
) and u
j
-
1
P
R
y
1 denote the path connecting u
j
-
1 and y
1 with internal vertices in R. Then we can get a cycle C
′
=
y
1
-
P
1
-
v
j
-
1
y
1
+
P
1
u
j
-
1
P
R
y
1 longer than C, a contradiction.Claim 9.
Consider the following:∑
i
=
0
m
d
P
(
v
i
)
≤
P
-
1 and ∑
i
=
0
m
d
P
(
v
i
)
+
∑
z
∈
R
I
d
P
(
z
)
≤
P
+
m
-
1.Proof.
Obviously,V
(
P
)
=
⋃
i
=
0
m
-
1
V
(
P
[
v
i
,
v
i
+
1
-
]
)
∪
V
(
P
[
v
m
,
y
]
) and ∑
i
=
0
m
d
P
(
v
i
)
=
d
U
(
P
). Then ∑
i
=
0
m
d
P
(
v
i
)
=
∑
i
=
0
m
-
1
d
U
(
P
[
v
i
,
v
i
+
1
-
]
)
+
d
U
(
P
[
v
m
,
y
]
). By Claim 5, d
U
(
P
[
v
m
,
y
]
)
≤
|
P
[
v
m
,
y
]
|
-
1. By Claim 4, d
U
(
P
[
v
i
,
v
i
+
1
-
]
)
≤
|
P
[
v
i
,
v
i
+
1
-
]
| for 1
≤
i
≤
m
-
1. Thus ∑
i
=
0
m
d
P
(
v
i
)
≤
∑
i
=
0
m
-
1
|
P
[
v
i
,
v
i
+
1
-
]
| + |
P
[
v
m
,
y
]
|
-
1
=
|
P
|
-
1.
Obviously,N
P
(
R
I
)
⊆
{
u
1
,
u
2
,
…
,
u
m
}. Then ∑
i
=
0
m
‍
d
P
(
v
i
)
+
∑
z
∈
R
I
d
P
(
z
)
=
d
U
(
P
)
+
∑
z
∈
R
I
‍
d
N
P
(
R
I
)
(
z
) = ∑
i
=
0
m
-
1
‍
(
d
U
(
P
[
v
i
,
v
i
+
1
-
]
)
+
∑
z
∈
R
I
‍
d
u
i
(
z
)
)
+
d
U
(
P
[
v
m
,
y
]
). Without loss of generality, we consider P
[
v
1
,
v
2
-
]. Let S
u
2 denote the U-segment containing u
2. By Claim 4, d
U
(
S
)
≤
|
S
| for any U-segment in P
[
v
1
,
v
2
-
]. Obviously, ∑
z
∈
R
I
‍
d
u
2
(
z
)
=
d
R
I
(
u
2
). By Claim 6, d
R
I
(
u
2
)
≤
2.
Supposed
U
(
u
2
)
=
0. Then u
2 is the first vertex in S
u
2 and S
u
2
=
C
[
u
2
,
v
2
). By Lemma 8(a), N
U
(
S
u
2
)
⊆
{
v
2
}. Thus d
U
(
S
u
2
)
=
S
u
2
-
1 and d
U
(
P
[
v
1
,
v
2
-
]
)
+
∑
z
∈
R
I
‍
d
u
2
(
z
)
=
∑
S
≠
S
u
2
‍
d
U
(
S
)
+
d
U
(
S
u
2
)
+
d
R
I
(
u
2
)
≤
∑
S
≠
S
u
2
‍
S + (
S
u
2
-
1
)
+
2
=
P
v
1
,
v
2
-
+
1.
Supposed
U
(
u
2
)
=
1. If d
R
I
(
u
2
)
≤
1, then d
U
(
P
[
v
1
,
v
2
-
]
)
+
∑
z
∈
R
I
‍
d
u
2
(
z
)
=
∑
S
≠
S
u
2
‍
d
U
(
S
)
+
d
U
(
S
u
2
)
+
d
R
I
(
u
2
) ≤ ∑
S
≠
S
u
2
‍
S
+
S
u
2
+
1
=
P
v
1
,
v
2
-
+
1. If d
R
I
(
u
2
)
=
2, then, by Claim 7, d
U
(
S
u
2
)
=
S
u
2
-
1. Thus d
U
(
P
[
v
1
,
v
2
-
]
)
+
∑
z
∈
R
I
‍
d
u
2
(
z
)
=
∑
S
≠
S
u
2
‍
d
U
(
S
)
+
d
U
(
S
u
2
)
+
d
R
I
(
u
2
)
≤
∑
S
≠
S
u
2
‍
S
+
(
S
u
2
-
1
) + 2
=
P
v
1
,
v
2
-
+
1.
Supposed
U
(
u
2
)
=
2. Then, by Claim 8, d
R
I
(
u
2
)
≤
1. Thus d
U
(
P
[
v
1
,
v
2
-
]
)
+
∑
z
∈
R
I
‍
d
u
2
(
z
) = ∑
S
≠
S
u
2
‍
d
U
(
S
)
+
d
U
(
S
u
2
)
+
d
R
I
(
u
2
)
≤
∑
S
≠
S
u
2
‍
|
S
|
+
|
S
u
2
|
+
1
=
|
P
[
v
1
,
v
2
-
]
|
+
1.
It follows thatd
U
(
P
[
v
1
,
v
2
-
]
)
+
∑
z
∈
R
I
‍
d
u
2
(
z
)
≤
P
v
1
,
v
2
-
+
1. Similarly, for any i
∈
[
1
,
m
-
1
], d
U
(
P
[
v
i
,
v
i
+
1
-
]
)
≤
P
v
i
,
v
i
+
1
-
+
1. By Claim 5, d
U
(
P
[
v
m
,
y
]
)
≤
|
P
[
v
m
,
y
]
|
-
1. Thus d
U
(
P
)
+
∑
z
∈
R
I
‍
d
P
(
z
)
≤
∑
i
=
0
m
-
1
‍
(
P
v
i
,
v
i
+
1
-
+
1
)
+
P
v
m
,
y
-
1
≤
|
P
|
+
m
-
1.Claim 10.
d
P
(
R
)
=
k and R is hamiltonian-connected for each component R of G
-
P.Proof.
N
G
-
P
(
v
i
)
∩
N
G
-
P
(
v
j
)
=
∅ from Lemma 8(a), for 0
≤
i
≠
j
≤
m, and then ∑
i
=
0
m
‍
d
G
-
P
(
v
i
)
≤
n
-
P
-
R. By the connectedness of G, m
≥
k. If m
≥
k
+
2, then we get an independent set {
v
0
,
v
1
,
…
,
v
m
} of order at least k
+
3. By Claim 9, ∑
i
=
0
m
‍
d
(
v
i
)
=
∑
i
=
0
m
‍
d
G
-
P
(
v
i
)
+
∑
i
=
0
m
‍
d
P
(
v
i
)
≤
(
n
-
P
-
R
)
+
(
|
P
|
-
1
)
=
n
-
1
-
R, a contradiction to σ
k
+
3
(
G
)
≥
n
+
2
k
-
2. Suppose m
=
k
+
1 and z
∈
V
(
R
). Then we can get an independent set {
z
,
v
0
,
v
1
,
…
,
v
m
} of order k
+
3. By Claim 9, d
P
(
z
)
+
∑
i
=
0
k
+
1
‍
d
P
(
v
i
)
≤
(
k
+
1
)
-
1
+
P
=
P
+
k. Then d
(
z
)
+
∑
i
=
0
k
+
1
‍
d
(
v
i
)
=
∑
i
=
0
k
+
1
‍
d
G
-
P
(
v
i
)
+
d
R
(
z
)
+
∑
i
=
0
k
+
1
‍
d
P
(
v
i
)
+
d
P
(
z
)
≤
(
n
-
|
P
|
-
|
R
|
)
+
(
|
R
|
-
1
)
+
(
|
P
|
+
k
) = n
+
k
-
1, a contradiction to σ
k
+
3
(
G
)
≥
n
+
2
k
-
2 by k
≥
2. Thus m
=
k.
Suppose thatR is not hamiltonian-connected. Then by Ore’s theorem [20], suppose z
1
,
z
2
∈
V
(
R
) with z
1
z
2
∉
E
(
G
) and d
R
(
z
1
)
+
d
R
(
z
2
)
≤
R. We can get an independent set {
z
1
,
z
2
,
v
0
,
v
1
,
…
,
v
k
} with order k
+
3. By Claim 9, d
(
z
1
)
+
d
(
z
2
)
+
∑
i
=
0
k
‍
d
(
v
i
)
=
d
R
(
z
1
)
+
d
R
(
z
2
)
+
∑
i
=
0
k
‍
d
G
-
P
(
v
i
)
+
(
∑
i
=
0
k
‍
d
P
(
v
i
)
+
d
P
(
z
1
)
+
d
P
(
z
2
)
) ≤ |
R
|
+
(
n
-
|
P
|
-
|
R
|
)
+
(
|
P
|
+
k
-
1
)
=
n
+
k
-
1, a contradiction to σ
k
+
3
(
G
)
≥
n
+
2
k
-
2 by k
≥
2.IfG
-
P contains only one component R, then, by Claim 10, there is a spanning 3-ended tree in G. Thus we only consider the case that G
-
P contains at least two components and suppose R
′ is a component in G
-
P
-
R.Claim 11.
Consider the following:N
R
′
(
v
i
)
≠
∅ for some i
∈
[
1
,
k
].Proof.
SupposeN
R
′
(
v
i
)
=
∅ for any i
∈
[
1
,
k
]. Then ∑
i
=
0
k
‍
d
G
-
P
(
v
i
)
≤
n
-
|
P
|
-
|
R
|
-
|
R
′
|. Let z
1
∈
V
(
R
), z
2
∈
V
(
R
′
). Then we get an independent set {
z
1
,
z
2
,
v
0
,
v
1
,
…
,
v
k
} of order k
+
3. By Claim 10, d
P
(
z
2
)
≤
k and, by Claim 9, ∑
i
=
0
k
‍
d
(
v
i
)
+
d
P
(
z
1
)
≤
|
P
|
+
k
-
1. Thus ∑
i
=
0
k
‍
d
(
v
i
)
+
d
(
z
1
)
+
d
(
z
2
) = d
P
(
z
2
)
+
d
R
(
z
1
)
+
d
R
′
(
z
2
)
+
(
∑
i
=
0
k
‍
d
P
(
v
i
)
+
d
P
(
z
1
)
)
+
∑
i
=
0
k
‍
d
G
-
P
(
v
i
)
≤
k
+
(
|
R
|
-
1
)
+
(
|
R
′
|
-
1
) + (
|
P
|
+
k
-
1
)
+
(
n
-
|
P
|
-
|
R
|
-
|
R
′
|
)
=
n
+
2
k
-
3, a contradiction to σ
k
+
3
(
G
)
≥
n
+
2
k
-
2.By Claim11, we assume N
R
′
(
v
i
)
≠
∅ for some i
∈
[
1
,
k
]. By Lemma 8(a), N
R
′
(
v
j
)
=
∅ for j
∈
[
0
,
i
-
1
]
∪
[
i
+
1
,
k
].Claim 12.
S
i
-
{
u
i
+
1
} contains a second noninsertible vertex v
i
′.Proof.
SupposeS
i
-
{
u
i
+
1
} contains only one noninsertible vertex v
i. Then we can get a path P
1
[
u
i
+
1
,
u
i
] such that V
(
P
1
)
=
V
(
C
)
-
{
v
i
} by inserting all the vertices in S
i
-
{
v
i
} to C
[
u
i
+
1
,
u
i
]. Suppose |
V
(
R
)
|
=
{
u
}. Then we get a cycle C
′
=
P
1
[
u
i
+
1
,
u
i
]
u
u
i
+
1. Let P
′
=
V
(
C
′
)
-
{
u
0
}. Then w
(
G
-
P
′
)
<
w
(
G
-
P
), a contradiction to (T1). Suppose |
V
(
R
)
|
≥
2. If N
R
(
u
i
)
∪
N
R
(
u
i
+
1
)
=
{
z
}, then N
P
(
R
)
∪
{
z
}
-
{
u
i
,
u
i
+
1
} is a vertex cut of G with order k
-
1, a contradiction to Claim 10. Thus N
R
u
i
∪
N
R
u
i
+
1
≥
2. By Claim 10, there is a hamiltonian path u
i
P
2
u
i
+
1 of R
∪
{
u
i
,
u
i
+
1
}. Thus we can get a cycle C
1
=
u
i
+
1
P
1
u
i
P
2
u
i
+
1 longer than C, a contradiction.Now, we complete the proof of Theorem5. By Claim 12 and Lemma 9, U
′
=
{
v
0
,
…
,
v
i
-
1
,
v
i
′
,
v
i
+
1
,
…
,
v
k
} is an independent set. Then, by the preceding proof, U
′ has the same properties as U. By Lemma 9, N
G
-
P
(
v
i
)
∩
N
G
-
P
(
v
j
)
=
∅, for any two distinct vertices v
i
,
v
j
∈
U
′. Thus ∑
v
∈
U
′
‍
d
G
-
P
(
v
)
≤
n
-
|
P
|
-
|
R
|
-
|
R
′
|. By Claim 9, ∑
v
∈
U
′
‍
d
P
(
v
)
≤
|
P
|
-
1. Let z
1
∈
V
(
R
), z
2
∈
V
(
R
′
). Then U
′
∪
{
z
1
,
z
2
} is an independent set of order k
+
3 in G. Thus ∑
v
∈
U
′
‍
d
(
v
)
=
∑
v
∈
U
′
‍
d
P
(
v
)
+
∑
v
∈
U
′
‍
d
G
-
P
(
v
)
≤
(
|
P
|
-
1
)
+
(
n
-
|
P
|
-
|
R
|
-
|
R
′
|
) = n
-
1
-
|
R
|
-
|
R
′
|. By Claim 10, d
(
z
1
)
≤
|
R
|
-
1
+
k, d
(
z
2
)
≤
|
R
′
|
-
1
+
k. Thus d
(
z
1
)
+
d
(
z
2
)
+
∑
v
∈
U
′
‍
d
(
v
) ≤ (
|
R
|
-
1
+
k
)
+
(
|
R
′
|
-
1
+
k
)
+
(
n
-
1
-
|
R
|
-
|
R
′
|
)
=
n
+
2
k
-
3, a contradiction to σ
k
+
3
(
G
)
≥
n
+
2
k
-
2. It follows that Theorem 5 holds.



---

*Source: 476182-2015-12-21.xml*