<p>A claw-free graph is a graph that does not contain <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(K_{1,3}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>K</mi> <mrow> <mn>1</mn> <mo>,</mo> <mn>3</mn> </mrow> </msub> </math></EquationSource> </InlineEquation> as an induced subgraph, and a 2-factor of a graph is a 2-regular spanning subgraph. In 1997, Ryjáček introduced the closure concept of claw-free graphs, and Hamilton cycles and related structures in claw-free graphs have been intensively studied via the closure concept. In this paper, using the closure concept, we show that for a claw-free graph <i>G</i> of order <i>n</i>, if every independent set <i>I</i> of <i>G</i> satisfies <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(|I|\le \delta _G(I)-1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mo stretchy="false">|</mo> <mi>I</mi> <mo stretchy="false">|</mo> </mrow> <mo>≤</mo> <msub> <mi>δ</mi> <mi>G</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>I</mi> <mo stretchy="false">)</mo> </mrow> <mo>-</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> and <i>G</i> satisfies <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(\sigma _k(G)\ge n\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>σ</mi> <mi>k</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>≥</mo> <mi>n</mi> </mrow> </math></EquationSource> </InlineEquation>, then <i>G</i> has a 2-factor with at most <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(k-1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>-</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> cycles, where <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(\delta _G(I)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>δ</mi> <mi>G</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>I</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> denotes the minimum degree of the vertices in <i>I</i>. As a corollary of the result, we show that every claw-free graph <i>G</i> with <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(\delta (G)\ge \alpha (G)+1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>δ</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo>≥</mo> <mi>α</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo>+</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> has a 2-factor with at most <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(\alpha (G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>α</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> cycles, which partially solves a conjecture by Faudree et al. in 2012. Furthermore, we show some results on 2-factors and degenerate cycle partitions of a claw-free graph <i>G</i> with <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(\sigma _k(G)\ge n\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>σ</mi> <mi>k</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>≥</mo> <mi>n</mi> </mrow> </math></EquationSource> </InlineEquation>.</p>

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

Degree sum conditions and a 2-factor with a bounded number of cycles in claw-free graphs

  • Masaki Kashima

摘要

A claw-free graph is a graph that does not contain \(K_{1,3}\) K 1 , 3 as an induced subgraph, and a 2-factor of a graph is a 2-regular spanning subgraph. In 1997, Ryjáček introduced the closure concept of claw-free graphs, and Hamilton cycles and related structures in claw-free graphs have been intensively studied via the closure concept. In this paper, using the closure concept, we show that for a claw-free graph G of order n, if every independent set I of G satisfies \(|I|\le \delta _G(I)-1\) | I | δ G ( I ) - 1 and G satisfies \(\sigma _k(G)\ge n\) σ k ( G ) n , then G has a 2-factor with at most \(k-1\) k - 1 cycles, where \(\delta _G(I)\) δ G ( I ) denotes the minimum degree of the vertices in I. As a corollary of the result, we show that every claw-free graph G with \(\delta (G)\ge \alpha (G)+1\) δ ( G ) α ( G ) + 1 has a 2-factor with at most \(\alpha (G)\) α ( G ) cycles, which partially solves a conjecture by Faudree et al. in 2012. Furthermore, we show some results on 2-factors and degenerate cycle partitions of a claw-free graph G with \(\sigma _k(G)\ge n\) σ k ( G ) n .