Affordable Access

Contraction theorems in Hamiltonian graph theory

Authors
Publisher
North-Holland
Publication Date
Disciplines
  • Mathematics

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.

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments

More articles like this

Contraction theorems in Hamiltonian graph theory

on Discrete Mathematics Jan 01, 1981

TWO THEOREMS IN GRAPH THEORY.

on Proceedings of the National Ac... Sep 15, 1957
More articles like this..