Forbidden Subgraphs and 2-Factors in Graphs
by
R. J. Faudree
Department of Mathematical Sciences, University of Memphis, Memphis, TN
Coauthors: J. R. Faudree, Department of Mathematics and Computer Science, University of Alaska at Fairbanks, Fairbanks, AK Z. Ryjáček, Department of Mathematics, University of West Bohemia, Plzeň, Czech Republic

The connected forbidden subgraphs and pairs of connected forbidden subgraphs that imply a 2-connected graph is hamiltonian have been characterized. A 2-factor of a graph of G is a spanning 2-regular subgraph of G (a vertex disjoint union of cycles). A characterization of forbidden connected graphs and pairs of forbidden connected graphs that imply that any (or a sufficiently large) 2-connected graph G has a 2-factor will be presented. Also presented will be a characterization of connected forbidden subgraphs and pairs of connected forbidden subgraphs that imply the existence of 2-factors with a predetermined number of components.

Date received: February 26, 2008