Closure for Spanning Trees with *k*-Ended Stems

Zheng Yan^{*}

Show more

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}*(

References

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

http://dx.doi.org/10.1016/j.disc.2007.04.019

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

http://dx.doi.org/10.1016/0012-365X(76)90078-9

[7] Broersma, H. and Tuinstra, H. (1998) Independence Trees and Hamilton Cycles. Journal of Graph Theory, 29, 227-237.

http://dx.doi.org/10.1002/(SICI)1097-0118(199812)29:4<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.

http://dx.doi.org/10.7151/dmgt.1534

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

http://dx.doi.org/10.1007/s00373-010-0973-2