Spanning Trees Whose Stems are Spiders

作者：Kano, Mikio; Yan, Zheng^*

来源：Graphs and Combinatorics, 2015, 31(6): 1883-1887.

DOI：10.1007/s00373-015-1618-2

• Spanning tree
• Spider
• Stem

Let T be a tree. The set of leaves of T is denoted by Leaf(T). The subtree is called the stem of T. A spider is a tree having at most one vertex with degree greater than two. In Gargano et al. (Discrete Math 285:83-95, 2004), it is shown that if a connected graph G satisfies (G) >=(vertical bar(G vertical bar - 1)/3, then G has a spanning spider. In this paper, we prove that if , then G has a spanning tree whose stem is a spider, where denotes the minimum degree sum of four vertices of G such that the distance between any two of their vertices are at least four. Moreover, we show that this condition is sharp.

• 出版日期2015-11