Degree Conditions for Spanning Brooms. Issue 3 (15th January 2014)

• Record Type: Journal Article
• Authors: Chen, Guantao; Ferrara, Michael; Hu, Zhiquan; Jacobson, Michael; Liu, Huiqing
• Is Part Of: Journal of graph theory. Volume 77:Issue 3(2014)
• Page Start: 237
• Page End: 250
• Publication Date: 2014-01-15
• Subjects: Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.21784
• Languages: English
• ISSNs: 0364-9024

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>A <italic>broom</italic> 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 <italic>G</italic> contains a spanning tree that is a broom. In this article, we give one solution to this problem by demonstrating that if <italic>G</italic> is a connected graph of order <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh177msszq" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21784:jgt21784-math-0001" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>n</mml:mi><mml:mo>≥</mml:mo><mml:mn>56</mml:mn></mml:mrow></mml:math></alternatives></inline-formula> with <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh177mstk5" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21784:jgt21784-math-0002" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>δ</mml:mi><mml:mrow><mml:mo>(</mml:mo><mml:mi>G</mml:mi><mml:mo>)</mml:mo></mml:mrow><mml:mo>≥</mml:mo><mml:mfrac><mml:mrow><mml:mi>n</mml:mi><mml:mo>−</mml:mo><mml:mn>2</mml:mn></mml:mrow><mml:mn>3</mml:mn></mml:mfrac></mml:mrow></mml:math></alternatives></inline-formula>, then <italic>G</italic> contains a spanning broom. This result is best possible.</p> </abstract>