New type degree conditions for a graph to have a 2-factor

2025/03/24 by Kashima, Masaki · 1 citation
#05C38 #05C45 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2503.18409

Abstract

A 2-factor of a graph is a 2-regular spanning subgraph. For a graph G and an independent set I of G, let δ_G(I) denote the minimum degree of vertices contained in I. We show that (1) if every independent set I of G satisfies |I|≤ δ_G(I)-1, then G has a 2-factor and that (2) if every independent set I of G satisfies |I|≤ δ_G(I), then G has a 2-factor unless G is isomorphic to a graph in completely determined exceptional graphs. It can be easily shown that the assumption of (1) is a relaxation of the Dirac condition on Hamiltonicity of graphs, and that the assumption of (2) is a relaxation of the Chvátal-Erdős condition on Hamiltonicity of graphs. Furthermore, for graphs with the assumption of (1), we show some results on a 2-factor with a bounded number of cycles.

Cited by

• A note on the number of non-cycle components in a pseudo 2-factor of graphs

Related

• 2-factors with k cycles in Hamiltonian graphs
• A Graph Invariant and 2-factorizations of a graph
• An updated survey on 2-Factors of Regular Graphs
• A note on the number of non-cycle components in a pseudo 2-factor of graphs
• Degree sum conditions and a 2-factor with a bounded number of cycles in claw-free graphs