Spanning Trees whose Stems have a Bounded Number of Branch Vertices

Zheng Yan

Discussiones Mathematicae Graph Theory (2016)

  • Volume: 36, Issue: 3, page 773-778
  • ISSN: 2083-5892

Abstract

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

How to cite

top

Zheng Yan. "Spanning Trees whose Stems have a Bounded Number of Branch Vertices." Discussiones Mathematicae Graph Theory 36.3 (2016): 773-778. <http://eudml.org/doc/285629>.

@article{ZhengYan2016,
abstract = {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.},
author = {Zheng Yan},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {spanning tree; stem; branch vertex},
language = {eng},
number = {3},
pages = {773-778},
title = {Spanning Trees whose Stems have a Bounded Number of Branch Vertices},
url = {http://eudml.org/doc/285629},
volume = {36},
year = {2016},
}

TY - JOUR
AU - Zheng Yan
TI - Spanning Trees whose Stems have a Bounded Number of Branch Vertices
JO - Discussiones Mathematicae Graph Theory
PY - 2016
VL - 36
IS - 3
SP - 773
EP - 778
AB - 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.
LA - eng
KW - spanning tree; stem; branch vertex
UR - http://eudml.org/doc/285629
ER -

References

top
  1. [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] Zbl1145.05017
  2. [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] Zbl1039.68095
  3. [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] Zbl1044.05048
  4. [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] Zbl1056.68587
  5. [5] M. Kano, M. Tsugaki and G. Yan, Spanning trees whose stems have bounded degrees, preprint. 
  6. [6] M. Kano and Z. Yan, Spanning trees whose stems have at most k leaves, Ars Combin. CXIVII (2014) 417-424. Zbl1349.05056
  7. [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] Zbl1183.05019
  8. [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] Zbl1298.05074
  9. [9] M. Tsugaki and Y. Zhang, Spanning trees whose stems have a few leaves, Ars Com- bin. CXIV (2014) 245-256. Zbl1324.05025

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.