Contraction theorems in Hamiltonian graph theory
Hoede, C. and Veldman, H.J. (1981) Contraction theorems in Hamiltonian graph theory. Discrete Mathematics, 34 (1). pp. 6167. ISSN 0012365X

PDF
640kB 
Abstract:  We prove that a kconnected 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 kconnected 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 1Hamiltonian, respectively. Conditions analogous to (*) guaranteeing the same properties were found by Chvátal and Erdös and by Lesniak. For traceable and 1Hamiltonian graphs the contraction theorems sharpen the corresponding analogues of (*), while equivalence is conjectured for Hamiltonian connected graphs. 
Item Type:  Article 
Copyright:  © 1981 Elsevier Science 
Link to this item:  http://purl.utwente.nl/publications/68715 
Official URL:  http://dx.doi.org/10.1016/0012365X(81)900224 
Export this item as:  BibTeX EndNote HTML Citation Reference Manager 
Repository Staff Only: item control page