Closure for Spanning Trees with <i>k</i>-Ended Stems

Abstract

Let T be a tree. The set of leaves of Τ is denoted by Leaf( Τ ) . The subtree Τ —Leaf( Τ ) of T 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 G be a connected graph and k ≥2 be an integer. Let u and ν be a pair of nonadjacent vertices in G . Suppose that | N G ( u )∪ N G ( v )|≥| G |- k -1 . Then G has a spanning tree with k -ended stem if and only if G + uv has a spanning tree with k -ended stem. Moreover, the condition on | N G ( u )∪ N G ( v )| is sharp.