The Independence Number Conditions for 2-Factors of a Claw-Free Graph

In 2014, some scholars showed that every 2-connected claw-free graph <i>G</i> with independence number <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>α</mi><mo>(</mo&g...

Full description

Bibliographic Details
Main Authors: Wanpeng Lei, Liming Xiong, Jun Yin
Format: Article
Language:English
Published: MDPI AG 2022-08-01
Series:Axioms
Subjects:
Online Access:https://www.mdpi.com/2075-1680/11/8/417
Description
Summary:In 2014, some scholars showed that every 2-connected claw-free graph <i>G</i> with independence number <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>α</mi><mo>(</mo><mi>G</mi><mo>)</mo><mo>≤</mo><mn>3</mn></mrow></semantics></math></inline-formula> is Hamiltonian with one exception of family of graphs. If a nontrivial path contains only internal vertices of degree two and end vertices of degree not two, then we call it a <i>branch</i>. A set <i>S</i> of branches of a graph <i>G</i> is called a <i>branch cut</i> if we delete all edges and internal vertices of branches of <i>S</i> leading to more components than <i>G</i>. We use a <i>branch bond</i> to denote a minimal branch cut. If a branch-bond has an odd number of branches, then it is called <i>odd</i>. In this paper, we shall characterize all 2-connected claw-free graphs <i>G</i> such that every odd branch-bond of <i>G</i> has an edge branch and such that <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>α</mi><mo>(</mo><mi>G</mi><mo>)</mo><mo>≤</mo><mn>5</mn></mrow></semantics></math></inline-formula> but has no 2-factor. We also consider the same problem for those 2-edge-connected claw-free graphs with <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>α</mi><mo>(</mo><mi>G</mi><mo>)</mo><mo>≤</mo><mn>4</mn></mrow></semantics></math></inline-formula>.
ISSN:2075-1680