ABSTRACT

Let be a tree. The set of leaves of is denoted by. The subtree of is called the stem of. A stem is called a k-ended stem if it has at most k-leaves in it. In this paper, we prove the following theorem. Let be a connected graph and be an integer. Let and be a pair of nonadjacent vertices in. Suppose that. Then has a spanning tree with k-ended stem if and only if has a spanning tree with k-ended stem. Moreover, the condition on is sharp.

Keywords:Closure, Spanning Tree, Stem, k-End Stem

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] .

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.

References