# Long cycles in graphs containing a 2-factor with many odd components

Heuvel van den, J. (1995) *Long cycles in graphs containing a 2-factor with many odd components.* Discrete Mathematics, 137 (1-3). pp. 389-393. ISSN 0012-365X

| PDF 194Kb |

Abstract: | We prove a result on the length of a longest cycle in a graph on n vertices that contains a 2-factor and satisfies d(u)+d(c)+d(w)n+2 for every tiple u, v, w of independent vertices. As a corollary we obtain the follwing improvement of a conjectre of Häggkvist (1992): Let G be a 2-connected graph on n vertices where every pair of nonadjacent vertices has degree sum at least n-k and assume G has a 2-factor with at least k+1 odd components. Then G is hamiltonian. |

Item Type: | Article |

Copyright: | © 1995 Elsevier Science |

Faculty: | Electrical Engineering, Mathematics and Computer Science (EEMCS) |

Research Group: | |

Link to this item: | http://purl.utwente.nl/publications/57340 |

Official URL: | http://dx.doi.org/10.1016/0012-365X(93)E0118-N |

Export this item as: | BibTeX EndNote HTML Citation Reference Manager |

Repository Staff Only: item control page