Contraction theorems in Hamiltonian graph theory

C. Hoede, H.J. Veldman

Research output: Contribution to journalArticleAcademic

6 Citations (Scopus)
62 Downloads (Pure)

Abstract

We prove that a k-connected graph (k>2) is Hamiltonian if it is not contractible to one of a specified collection of graphs of order 2k+1. The theorem generalizes a previous result of the authors. The proof partly parallels that of the following, less general, result of Chvátal and Erdös: A k-connected graph containing no independent set of more than k points (k>2) is Hamiltonian (*). Also stated in terms of contractibility are sufficient conditions for graphs to be traceable, Hamiltonian connected or 1-Hamiltonian, respectively. Conditions analogous to (*) guaranteeing the same properties were found by Chvátal and Erdös and by Lesniak. For traceable and 1-Hamiltonian graphs the contraction theorems sharpen the corresponding analogues of (*), while equivalence is conjectured for Hamiltonian connected graphs.
Original languageEnglish
Pages (from-to)61-67
JournalDiscrete mathematics
Volume34
Issue number1
DOIs
Publication statusPublished - 1981

Keywords

  • IR-68715

Fingerprint

Dive into the research topics of 'Contraction theorems in Hamiltonian graph theory'. Together they form a unique fingerprint.

Cite this