Premium
Degree Conditions for Spanning Brooms
Author(s) -
Chen Guantao,
Ferrara Michael,
Hu Zhiquan,
Jacobson Michael,
Liu Huiqing
Publication year - 2014
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21784
Subject(s) - broom , spanning tree , combinatorics , mathematics , minimum degree spanning tree , graph , degree (music) , minimum spanning tree , enhanced data rates for gsm evolution , connectivity , tree (set theory) , connected dominating set , order (exchange) , discrete mathematics , computer science , geography , telecommunications , physics , archaeology , finance , acoustics , economics
A broom is a tree obtained by subdividing one edge of the star an arbitrary number of times. In (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) Flandrin et al. posed the problem of determining degree conditions that ensure a connected graph G contains a spanning tree that is a broom. In this article, we give one solution to this problem by demonstrating that if G is a connected graph of order n ≥ 56 with δ ( G ) ≥ n − 2 3 , then G contains a spanning broom. This result is best possible.