Planar and infinite hypohamiltonian and hypotraceable graphs

https://doi.org/10.1016/0012-365X(76)90071-6Get rights and content
Under an Elsevier user license
open archive

Abstract

Chvátal raised the question whether or not planar hypohamiltonian graphs exist and Grünbaum conjectured the nonexistence of such graphs. We shall describe an infinite class of planar hypohamiltonian graphs and infinite classes of planar hypotraceable graphs of connectivity two (resp. three). Infinite hypohamiltonian (resp. htpotraceable) graphs are also described. It is shown how the study of infinite hypotraceable graphs leads to a new infinite family of finite hypotraceable graphs.

Cited by (0)