Spanning Trees whose Stems have a Bounded Number of Branch Vertices

• Autorzy: Zheng Yan
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

spanning tree; stem; branch vertex

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2016
• Tom: 36
• Numer: 3
• Strony: 773-778

Daty

wydano

2016-08-01

otrzymano

2015-06-01

poprawiono

2015-10-29

zaakceptowano

2015-11-19

online

2016-07-06

Twórcy

autor

Zheng Yan

• Institute of Applied Mathematics Yangtze University, Jingzhou, Hubei, China

Bibliografia

• [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]
• [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]
• [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]
• [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]
• [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.
• [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]
• [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]
• [9] M. Tsugaki and Y. Zhang, Spanning trees whose stems have a few leaves, Ars Com- bin. CXIV (2014) 245-256.

Identyfikatory

DOI

10.7151/dmgt.1885