<p>A cycle <i>C</i> of a graph <i>G</i> is nice if <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(G-V(C)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>G</mi> <mo>-</mo> <mi>V</mi> <mo stretchy="false">(</mo> <mi>C</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> has a perfect matching. A graph <i>G</i> is called even (odd) cycle-nice if each even (odd) cycle of <i>G</i> is nice. (Wang et al. Discrete Mathematics, 345(7):112876, 2022), (S.&#xa0;Zhang et al. Discrete Mathematics &amp; Theoretical Computer Science 2020) studied 2-connected even cycle-nice claw-free graphs. In this paper, we investigate odd cycle-nice graphs and then only consider non-bipartite graphs. We show that a 2-connected odd cycle-nice non-bipartite graph is factor-critical. We completely characterize the structure of 2-connected odd cycle-nice claw-free non-bipartite graphs by three types of operations.</p>

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

Odd cycle-nice claw-free graphs

  • Huilin Pan,
  • Yan Liu

摘要

A cycle C of a graph G is nice if \(G-V(C)\) G - V ( C ) has a perfect matching. A graph G is called even (odd) cycle-nice if each even (odd) cycle of G is nice. (Wang et al. Discrete Mathematics, 345(7):112876, 2022), (S. Zhang et al. Discrete Mathematics & Theoretical Computer Science 2020) studied 2-connected even cycle-nice claw-free graphs. In this paper, we investigate odd cycle-nice graphs and then only consider non-bipartite graphs. We show that a 2-connected odd cycle-nice non-bipartite graph is factor-critical. We completely characterize the structure of 2-connected odd cycle-nice claw-free non-bipartite graphs by three types of operations.