<p>For any integer <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10801_2025_1396_Article_IEq1.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="42" /> </InlineMediaObject> <EquationSource Format="TEX">\(k\ge 1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>≥</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>, a graph <i>G</i> is said to be <i>k</i>-factor-critical if <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10801_2025_1396_Article_IEq2.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="49" /> </InlineMediaObject> <EquationSource Format="TEX">\(G-S\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>G</mi> <mo>-</mo> <mi>S</mi> </mrow> </math></EquationSource> </InlineEquation> has a perfect matching for each <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10801_2025_1396_Article_IEq3.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="75" /> </InlineMediaObject> <EquationSource Format="TEX">\(S\subseteq V(G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>S</mi> <mo>⊆</mo> <mi>V</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> with <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10801_2025_1396_Article_IEq4.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="57" /> </InlineMediaObject> <EquationSource Format="TEX">\(|S|=k\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">|</mo> <mi>S</mi> <mo stretchy="false">|</mo> <mo>=</mo> <mi>k</mi> </mrow> </math></EquationSource> </InlineEquation>. In this paper, we present a sufficient condition in terms of the number of <i>r</i>-cliques to guarantee a graph with minimum degree at least <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10801_2025_1396_Article_IEq5.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="12" /> </InlineMediaObject> <EquationSource Format="TEX">\(\delta \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>δ</mi> </math></EquationSource> </InlineEquation> to be <i>k</i>-factor-critical, which improves the result of Fan and Lin (Spectral conditions for <i>k</i>-extendability and <i>k</i>-factors of bipartite graphs, <a href="http://arxiv.org/abs/2211.09304">arXiv: 2211.09304</a>). For any integer <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10801_2025_1396_Article_IEq6.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="47" /> </InlineMediaObject> <EquationSource Format="TEX">\(k\ge 2,\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>≥</mo> <mn>2</mn> <mo>,</mo> </mrow> </math></EquationSource> </InlineEquation> a spanning <i>k</i>-tree of a connected graph <i>G</i> is a spanning tree in which every vertex has degree at most <i>k</i>. Neumann–Lara and Rivera–Campo (Combinatorica 11:55–61, 1991) proved that, for an <i>m</i>-connected graph <i>G</i> with <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10801_2025_1396_Article_IEq7.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="47" /> </InlineMediaObject> <EquationSource Format="TEX">\(m\ge 2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>m</mi> <mo>≥</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>, if its independence number <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10801_2025_1396_Article_IEq8.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="154" /> </InlineMediaObject> <EquationSource Format="TEX">\(\alpha (G)\le (k-1)m+1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>α</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo>≤</mo> <mo stretchy="false">(</mo> <mi>k</mi> <mo>-</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mi>m</mi> <mo>+</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>, then <i>G</i> contains a spanning <i>k</i>-tree. Motivated by the above result, we provide tight spectral conditions for an <i>m</i>-connected graph to contain a spanning <i>k</i>-tree.</p>

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

Sufficient conditions for k-factor-critical graphs and spanning k-trees of graphs

  • Guoyan Ao,
  • Ruifang Liu,
  • Jinjiang Yuan

摘要

For any integer \(k\ge 1\) k 1 , a graph G is said to be k-factor-critical if \(G-S\) G - S has a perfect matching for each \(S\subseteq V(G)\) S V ( G ) with \(|S|=k\) | S | = k . In this paper, we present a sufficient condition in terms of the number of r-cliques to guarantee a graph with minimum degree at least \(\delta \) δ to be k-factor-critical, which improves the result of Fan and Lin (Spectral conditions for k-extendability and k-factors of bipartite graphs, arXiv: 2211.09304). For any integer \(k\ge 2,\) k 2 , a spanning k-tree of a connected graph G is a spanning tree in which every vertex has degree at most k. Neumann–Lara and Rivera–Campo (Combinatorica 11:55–61, 1991) proved that, for an m-connected graph G with \(m\ge 2\) m 2 , if its independence number \(\alpha (G)\le (k-1)m+1\) α ( G ) ( k - 1 ) m + 1 , then G contains a spanning k-tree. Motivated by the above result, we provide tight spectral conditions for an m-connected graph to contain a spanning k-tree.