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

J. van den Heuvel

Research output: Contribution to journalArticleAcademic

68 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)389-393
JournalDiscrete mathematics
Volume137
Issue number1-3
DOIs
Publication statusPublished - 1995

Keywords

  • IR-57340

Fingerprint Dive into the research topics of 'Long cycles in graphs containing a 2-factor with many odd components'. Together they form a unique fingerprint.

Cite this