zbMATH — the first resource for mathematics

New constructions of hypohamiltonian and hypotraceable graphs. (English) Zbl 1386.05102
Summary: A graph \(G\) is hypohamiltonian/hypotraceable if it is not Hamiltonian/traceable, but all vertex-deleted subgraphs of \(G\) are Hamiltonian/traceable. All known hypotraceable graphs are constructed using hypohamiltonian graphs; here we present a construction that uses so-called almost hypohamiltonian graphs (nonhamiltonian graphs, whose vertex-deleted subgraphs are Hamiltonian with exactly one exception). This construction is an extension of a method of C. Thomassen [Discrete Math. 9, 91–96 (1974; Zbl 0278.05110)]. As an application, we construct a planar hypotraceable graph of order 138, improving the best-known bound of 154. We also prove a structural type theorem showing that hypotraceable graphs possessing some connectivity properties are all built using either Thomassen’s or our method. We also prove that if \(G\) is a Grinbergian graph without a triangular region, then \(G\) is not maximal nonhamiltonian and using the proof method we construct a hypohamiltonian graph of order 36 with crossing number 1, improving the best-known bound of 46.

05C45 Eulerian and Hamiltonian graphs
Full Text: DOI