Closure for Spanning Trees with k-Ended Stems


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.

Conflicts of Interest

The authors declare no conflicts of interest.


[1] Kano, M., Tsugaki, M. and Yan, G.Y. Spanning Trees Whose Stems Have Bounded Degrees. Preprint.
[2] Bondy, J.A. (1980) Longest Paths and Cycles in Graphs with High Degree. Research ReportCORR80-16, Department of Combinatorics and Optimization, University of Waterloo, Waterloo.
[3] Yamashita T. (2008) Degree Sum and Connectivity Conditions for Dominating Cycles. Discrete Mathematics, 308, 1620-1627.
[4] Tsugaki, M. and Zhang, Y. Spanning Trees Whose Stems Have a Few Leaves. Preprint.
[5] Kano, M. and Yan, Z. Spanning Trees Whose Stems Have at Most Leaves. Preprint.
[6] Bondy, J.A. and Chvátal, V. (1976) A Mothod in Graph Theory. Discrete Mathematics, 15, 111-135.
[7] Broersma, H. and Tuinstra, H. (1998) Independence Trees and Hamilton Cycles. Journal of Graph Theory, 29, 227-237.<227::AID-JGT2>3.0.CO;2-W
[8] Fujisawa, J., Saito, A. and Schiermeyer, I. (2011) Closure for Spanning Trees and Distant Area. Discussiones Mathematicae Graph Theory, 31, 143-159.
[9] Broersma, H., Ryjácek, Z. and Schiermeyer, I. (2000) Closure Concepts: A Survey. Graphs and Combinatorics, 16, 17-48.
[10] Akiyama, J. and Kano, M. (2011) Factors and Factorizations of Graphs, Lecture Note in Mathematics (LNM 2031), Springer.
[11] Ozeki, K. and Ya-mashita, T. (2011) Spanning Trees—A Survey. Graphs Combinatorics, 22, 1-26.

Copyright © 2023 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.