Let T be a tree, a vertex of degree one and a vertex of degree at least three is called a leaf and a branch vertex, respectively. The set of leaves of T is denoted by Leaf(T). The subtree T − Leaf(T) of T is called the stem of T and denoted by Stem(T). In this paper, we give two sufficient conditions for a connected graph to have a spanning tree whose stem has a bounded number of branch vertices, and these conditions are best possible.
@article{bwmeta1.element.doi-10_7151_dmgt_1885,
author = {Zheng Yan},
title = {Spanning Trees whose Stems have a Bounded Number of Branch Vertices},
journal = {Discussiones Mathematicae Graph Theory},
volume = {36},
year = {2016},
pages = {773-778},
zbl = {1339.05212},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1885}
}
Zheng Yan. Spanning Trees whose Stems have a Bounded Number of Branch Vertices. Discussiones Mathematicae Graph Theory, Tome 36 (2016) pp. 773-778. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1885/
[1] E. Flandrin, T. Kaiser, R. Kužel, H. Li and Z. Ryjǎćek, Neighborhood unions and extremal spanning trees, Discrete Math. 308 (2008) 2343-2350. doi:10.1016/j.disc.2007.04.071[WoS][Crossref] | Zbl 1145.05017
[2] L. Gargano and M. Hammar, There are spanning spiders in dense graphs (and we know how to find them), Lect. Notes Comput. Sci. 2719 (2003) 802-816. doi:10.1007/3-540-45061-0 63[Crossref] | Zbl 1039.68095
[3] L. Gargano, M. Hammar, P. Hell, L. Stacho and U. Vaccaro, Spanning spiders and light-splitting switchs, Discrete Math. 285 (2004) 83-95. doi:10.1016/j.disc.2004.04.005[Crossref] | Zbl 1044.05048
[4] L. Gargano, P. Hell, L. Stacho and U. Vaccaro, Spanning trees with bounded number of branch vertices, Lect. Notes Comput. Sci. 2380 (2002) 355-365. doi:10.1007/3-540-45465-9 31[Crossref] | Zbl 1056.68587
[5] M. Kano, M. Tsugaki and G. Yan, Spanning trees whose stems have bounded degrees, preprint.
[6] M. Kano and Z. Yan, Spanning trees whose stems have at most k leaves, Ars Combin. CXIVII (2014) 417-424. | Zbl 1349.05056
[7] A. Kyaw, Spanning trees with at most 3 leaves in K1 , 4-free graphs, Discrete Math. 309 (2009) 6146-6148. doi:10.1016/j.disc.2009.04.023[Crossref] | Zbl 1183.05019
[8] H. Matsuda, K. Ozeki and T. Yamashita, Spanning trees with a bounded number of branch vertices in a claw-free graph, Graphs Combin. 30 (2014) 429-437. doi:10.1007/s00373-012-1277-5[Crossref] | Zbl 1298.05074
[9] M. Tsugaki and Y. Zhang, Spanning trees whose stems have a few leaves, Ars Com- bin. CXIV (2014) 245-256. | Zbl 1324.05025