Closure for Spanning Trees with k-Ended Stems

HTML  Download Download as PDF (Size: 919KB)  PP. 55-59  
DOI: 10.4236/ojdm.2014.43008    4,292 Downloads   5,615 Views  Citations
Author(s)

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 |NG(u)∪NG(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 |NG(u)∪NG(v)| is sharp.

Share and Cite:

Yan, Z. (2014) Closure for Spanning Trees with k-Ended Stems. Open Journal of Discrete Mathematics, 4, 55-59. doi: 10.4236/ojdm.2014.43008.

Copyright © 2024 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.