Forbidden Subgraphs for Existences of (Connected) 2-Factors of a Graph

Abstract

Clearly, having a 2-factor in a graph is a necessary condition for a graph to be hamiltonian, while having an even factor in graph is a necessary condition for a graph to have a 2-factor. In this paper, we completely characterize the forbidden subgraph and pairs of forbidden subgraphs that force a 2-connected graph admitting a 2-factor (a necessary condition) to be hamiltonian and a connected graph with an even factor (a necessary condition) to have a 2-factor, respectively. Our results show that these pairs of forbidden subgraphs become wider than those in Faudree, Gould and in Fujisawa, Saito, respectively, if we impose the two necessary conditions, respectively.

Keywords

• forbidden subgraph
• even factor
• 2-factor
• hamiltonian
• 05c38
• 05c45