×

Small hypohamiltonian graphs. (English) Zbl 0880.05061

A graph is hypohamiltonian if it has no hamiltonian cycle but every vertex-deleted subgraph has a hamiltonian cycle. More than 20 years ago it was shown that there exists no hypohamiltonian graph of order 14, 12, 11 or less than 10, and that there exists one of each other order, except possibly 17. The present paper describes all hypohamiltonian graphs with at most 18 vertices. There are none on 17 vertices.

MSC:

05C45 Eulerian and Hamiltonian graphs
PDF BibTeX XML Cite