Degree Conditions for Spanning Brooms. Issue 3 (15th January 2014) - Chen, Guantao; Ferrara, Michael; Hu, Zhiquan; Jacobson, Michael; Liu, Huiqing
Abstract 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 <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh177msszq" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />n≥56</alternatives> with <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh177mstk5" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />δ(G)≥n−23</alternatives>, then G contains a spanning broom. This result is best possible.