1. Introduction
We consider simple graphs, which have neither loops nor multiple edges. For a graph
, let 
and 
denote the set of vertices and the set of edges of
, respectively. We write 
for the order of 
(i.e.,
). For a vertex 
of
, the degree of 
in 
is denoted by
, and the set of vertices adjacent to 
is called the neighborhood of 
and denoted by
. In particular,
. An edge joining two vertices 
and 
is denoted by 
or
.
Let 
be a tree. A vertex of 
with degree one is often called a leaf of
, and the set of leaves of 
is denoted by
. The subtree 
of 
is called the stem of 
and denoted by
. A spanning tree with specified stem was first considered in [1] .
A tree having at most 
leaves is called a k-ended tree. So a tree whose stem has at most 
leaves in it is called a tree with k-ended stem. Notice that a tree with 2-ended stem is nothing but a caterpillar, whose stem is a path. We consider a spanning tree with k-ended stem.
We make a remark about spanning trees with k-ended stem from the point of view of dominating set. A subgraph 
of a graph 
is said to dominate 
if every vertex of 
not contained in 
has a neighbor in
. Namely, 
dominates 
if every vertex 
satisfies
. So a graph 
has a spanning tree with k-ended stem if and only if 
has a k-ended tree that dominates
. There are many researches on dominating cycles and dominating paths (for example, see [2] and [3] with stronger definition of domination). Thus the concept of spanning trees with k-ended stem can be also considered as a generalization of dominating paths.
For an integer 
and a graph
, 
denotes the minimum degree sum of 
independent vertices of
. The following theorem gives a sufficient condition using 
for a graph to have a spanning tree with k-ended stem.
Theorem 1 (Tsugaki and Zhang [4] ) Let 
be a connected graph and 
be an integer. If
then 
has a spanning tree with k-ended stem.
Another result on spanning trees with k-ended stem is the following.
Theorem 2 (Kano and Yan [5] ) Let 
be a connected graph and 
be an integer. If 
satisfies one of the following conditions, then 
has a spanning tree with k-ended stem.
(1) 
(2) 
is claw-free and
.
A closure operation is useful in the study of the existence of hamiltonian cycles, hamiltonian paths and other spanning subgraphs in graphs. It was first introduced by Bondy and Chvátal.
Theorem 3 (Bondy and Chval [6] ) Let 
be a graph and let 
and 
be two nonadjacent vertices of
.
(1) Suppose
. Then 
has a hamiltonian cycle if and only if 
has a hamiltonian cycle.
(2) Suppose
. Then 
has a hamiltonian path if and only if 
has a hamiltonian path.
After [6] , many researchers have defined other closure concepts for various graph properties. The following theorem gives a result on closure for spanning k-ended tree.
Theorem 4 (Broersma and Tuinstra [7] ) Let 
be an integer, and let G be a graph. Let 
and 
be a pair of nonadjacent vertices of 
with
. Then 
has a spanning k-ended tree if and only if 
has a spanning 
-ended tree.
Another type of closure theorem on spanning k-ended tree can be found in Fujisawa, Saito and Schiermeyer [8] . The interested reader is referred to the survey [9] on closure concepts.
In this paper, we prove the following theorem.
Theorem 5 Let 
be a connected graph and 
be an integer. Let 
and 
be a pair of nonadjacent vertices of 
such that
(1)
Then 
has a spanning tree with k-ended stem if and only if 
has a spanning tree with k-ended stem.
Before proving Theorem 5, we show that the condition (1) in Theorem 5 is sharp. We construct a graph 
as follows. Let 
and 
be integers, and let 
be a complete graph of order
, which is a subgraph of
. Let 
be 
vertices of 
not contained in
. Join 
and 
to all the vertices of 
by edges. Join 
to 
and 
by edges. Then the resulting graph is 
(see Figure 1). It is immediate that 
has a spanning tree with k-ended stem, where all the vertices of 
and 
are leaves of the spanning tree, and
. However 
has no spanning tree with k-ended stem. Therefore the condition (1) is sharp. Moreover, in Figure 1, 
. Since 
be an arbitrary integer, the degree sum of 
and 
can be arbitrarily great. This implies that we can not find a condition similar to Theorem 4 for spanning tree with k-ended stem.
Some results on spanning k-ended trees and other spanning trees with given properties can be found in [10] , and many current results on spanning trees can be found in [11] .
Figure 1. A graph G having no spanning tree with k-ended stem.
2. Proof of Theorem 5
In this section we prove Theorem 5. Without mentioning, we often use the fact that 
is a disjoint union of 
and
.
Proof of Theorem 5. Since the necessity of the theorem is trivial, we only prove the sufficiency. Assume, to the contrary, that 
has a spanning tree with k-ended stem but 
does not have a spanning tree with kended stem. Let us denote
. Choose a spanning tree 
with k-ended stem of 
so that
(T1) 
is as small as possible, and
(T2) 
is as small as possible subject to (T1).
It is obvious that the edge 
is contained in 
since otherwise 
is a spanning tree with k-ended stem of
. Let
. Then obviously
.
Claim 1. (1) 
is an independent set of
; (2) For every
, there exists a vertex 
that is adjacent to 
in 
and
.
By the choice (T1), it is easy to see that if
, then 
is an independent set of
, and so is of
. Assume that 
and the two leaves 
and 
of 
are adjacent in
. It is easy to see that 
and 
are not adjacent in 
since otherwise we can obtain a spanning tree with 2-ended stem of 
from
. If 
and 
are both contained in
, then 
is a spanning tree with 2-ended stem of
, which contradicts the assumption. Hence we may assume that 
is a vertex of 
and 
is a leaf of 
by symmetry of 
and 
and by
. Since 
is connected, 
is adjacent to a vertex
. If 
is contained in
, then 
is a spanning tree with 2-ended stem of
, a contradiction. If 
is a leaf of
, let 
be the vertex of 
adjacent to 
in
, and let 
be a vertex of 
adjacent to
. Then 
is a spanning tree with 2-ended stem of
, a contradiction. Therefore, 
is an independent set of
. Hence (1) of Claim 1 follows.
Suppose that there exists a vertex
, 
, such that every leaf 
adjacent to 
in 
satisfies
. Then for every leaf 
adjacent to 
in
, remove the edge 
from 
and add an edge 
of
, where
. Denote the resulting tree of 
by
.
Then 
is a spanning tree of 
and satisfies
, which contradicts the condition
(T2). Therefore, (2) of Claim 1 holds.
Hereafter, we take the vertices 
as in Claim 1(2). Let
. Since the edge 
is contained in
, let
, where 
and
. Since 
is a connected graph, there exist a vertex 
and a vertex 
which are adjacent in
.
Claim 2.
.
The claim holds when
, and so we assume that
. If
, then 
is a spanning tree with k-ended stem of
, which contradicts the assumption. Next we consider the case where
. If either 
is a leaf of 
or the degree of 
in 
is 1 or greater than 2, then 
is a spanning tree with k-ended stem of
, which contradicts the assumption. Thus the degree of 
in 
is 2. By symmetry of 
and
, we may assume that the degree of 
in 
is also 2, and it is clear that 
is an edge of
.
First we consider 
and
. If a vertex 
is adjacent to 
in
, then 
is a spanning tree with k-ended stem of
, a contradiction. Thus no vertex of 
is adjacent to 
in
. By symmetry of 
and
, no vertex of 
is adjacent to 
in
. Assume that a vertex 
is adjacent to 
in 
and 
contains at least two vertices of
. Then the path in 
connecting 
and 
contains a vertex of degree at least 3 in
. Let 
be an edge of the path which is incident with a vertex with degree at least 3 in
. Then 
is a spanning tree with k-ended stem of
, and 
has degree at least 3 in
. Then we can derive a contradiction by the same argument as in the above first paragraph. Therefore if a vertex 
of 
is adjacent to 
in
, then 
contains exactly one vertex of
. Note that 
may be adjacent to 
but not to
. Since 
by
, 
contains at least two vertices of
, which means no vertex of 
is adjacent to 
in 
by the same argument on 
and 
given above.
By the above fact and Claim (1), we obtain
which implies 
by 
and
, which contradicts (1).
Next we consider the case where 
and
. In this case, 
is a path, and let 
and 
be the leaves of 
where 
and
. By the same argument as in the above paragraph, we have that neither 
and 
nor 
and 
are adjacent in
. We shall show that 
and 
are not adjacent in
. Assume that 
and 
are adjacent in
. Let 
be the vertex adjacent to 
in 
if 
or 
if
, and let 
be a vertex adjacent to 
in
. Then 
is a spanning tree with 3-ended stem of
, a contradiction. Similarly, 
and 
are not adjacent in
.
By the above fact and Claim 1, we obtain
which implies 
by
, which contradicts (1). Hence Claim 2 holds.
We consider the following two cases:
Case 1. 
and 
are both contained in
.
Subcase 1.1 Both 
are 
are vertices of
.
In this case, by Claim 1 (2), we have
then 
by Claim 2, which contradicts (1).
Subcase 1.2 
is a leaf of 
and 
is a vertex of
.
In this case, without loss of generality, let
. If either 
has degree greater than 2 in 
or
, then 
is a spanning tree with k-ended stem of
, which is a contradiction. Hence 
has degree 2 in 
and
.
Let 
be the vertex adjacent to 
in 
if 
or 
if
. Then 
, since otherwise, 
is a spanning tree with k-ended stem of
. Let 
be the path connecting 
and 
in
. Then there exists at least one vertex 
such that 
pass through
. We assign an orientation in 
from 
to
, and 
be the successor of
. If 
and 
are adjacent in
, then 
is a spanning tree with k-ended stem of
, which contradicts the assumption. Therefore, by Claim 1(2), we have
Then
, which contradicts (1).
Case 2. 
is a vertex of 
and 
is a leaf of
.
Subcase 2.1 
is a leaf of
.
In this case, if 
is adjacent to a vertex 
in
, where 
is a vertex of
, then 
is a spanning tree with k-ended stem of
, which contradicts the assumption. So the neighborhood of 
is contained in
. Without loss of generality, let 
and
.
By Claim 1 (2), we have
Hence
That means
, which contradicts (1).
Subcase 2.2 
is a vertex of
.
In this case, by Claim 1 (2),
. If there exists some 
such that
, then 
is a spanning tree with k-ended stem of
, which contradicts the assumption. Hence
. We have
then
, which contradicts (1).
Consequently, the proof is complete. ,
Acknowledgments
The author would like to thank Prof. Mikio Kano for introducing me to problems on spanning trees with specified stems and for his valuable suggestions.