Scholarlink

<p>If one edge of a claw is subdivided, the resulting graph is called a <i>chair</i>. Spanning trees in claw-free graphs have been widely studied, but we are unable to find prior results on spanning trees in chair-free graphs. We show two sufficient conditions for a connected chair-free graph to have a spanning tree with a bounded number of branch vertices. First, a connected chair-free graph has a spanning tree with at most <i>k</i> branch vertices if its independence number is at most <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2945_Article_IEq1.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="47" /> </InlineMediaObject> <EquationSource Format="TEX">\( 2k+2 \)</EquationSource> </InlineEquation>. Second, if a connected chair-free graph of order <i>n</i> has a spanning tree with at most 4 leaves and the degree sum of any five independent vertices is at least <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2945_Article_IEq2.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="41" /> </InlineMediaObject> <EquationSource Format="TEX">\( n-2 \)</EquationSource> </InlineEquation>, then the graph has a spanning tree with at most one branch vertex. Similarities and differences between claw-free and chair-free graphs are discussed, and several related conjectures are proposed.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Spanning Trees with Few Branch Vertices in a Chair-Free Graph

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年8月26日

查看全文
  • Janee Schrader,
  • Warren Shull

摘要

If one edge of a claw is subdivided, the resulting graph is called a chair. Spanning trees in claw-free graphs have been widely studied, but we are unable to find prior results on spanning trees in chair-free graphs. We show two sufficient conditions for a connected chair-free graph to have a spanning tree with a bounded number of branch vertices. First, a connected chair-free graph has a spanning tree with at most k branch vertices if its independence number is at most \( 2k+2 \) . Second, if a connected chair-free graph of order n has a spanning tree with at most 4 leaves and the degree sum of any five independent vertices is at least \( n-2 \) , then the graph has a spanning tree with at most one branch vertex. Similarities and differences between claw-free and chair-free graphs are discussed, and several related conjectures are proposed.