Hypohamiltonian graphs

A graph G is hypohamiltonian if G is non-hamiltonian and G-v is hamiltonian for every vertex v of G.

The graph lists are currently only available in 'graph6' format.

The following lists are available:

Reza Jooyandeh also maintains a page with lists of planar hypohamiltonian graphs. This page can be found here.

Lists of almost hypohamiltonian graphs can be found here.

Hypohamiltonian graphs

All results up to 17 vertices were independently verified by Aldred, McKay and Wormald [1] and Goedgebeur and Zamfirescu [2]. The results with more than 17 vertices were obtained with the program GenHypohamiltonian of Goedgebeur and Zamfirescu [2].

The following table gives the complete lists of all hypohamiltonian graphs with a given lower bound on the girth. The counts of cases which are indicated with a '≥' in the table are possibly incomplete. In all other cases the numbers are the counts of the complete sets of hypohamiltonian graphs.

Vertices girth ≥ 3 girth ≥ 4 girth ≥ 5 girth ≥ 6 girth ≥ 7 girth ≥ 8
0-9 0 0 0 0 0 0
10 1 1 1 0 0 0
11 0 0 0 0 0 0
12 0 0 0 0 0 0
13 1 1 1 0 0 0
14 0 0 0 0 0 0
15 1 1 1 0 0 0
16 4 4 4 0 0 0
17 0 0 0 0 0 0
18 14 13 8 0 0 0
19 34 34 34 0 0 0
20 ? ≥ 98 4 0 0 0
21 ? ? 85 0 0 0
22 ? ? 420 0 0 0
23 ? ? 85 0 0 0
24 ? ? 2530 0 0 0
25 ? ? ? 1 0 0
26 ? ? ? 0 0 0
27 ? ? ? ? 0 0
28 ? ? ? ≥ 2 1 0
29 ? ? ? ? 0 0
30 ? ? ? ? 0 0
31-35 ? ? ? ? ? 0

Cubic hypohamiltonian graphs

The graphs in this section were obtained by applying a generator for cubic graphs (see the cubic graphs page) and testing the generated graphs for hypohamiltonicity as a filter.

The following table give the complete lists of all cubic hypohamiltonian graphs with a given lower bound on the girth. (Note that cubic hypohamiltonian graphs must have girth at least 4). More information about these graphs can be found in [2].

Vertices girth ≥ 4 girth ≥ 5 girth ≥ 6 girth ≥ 7
0-9 0 0 0 0
10 1 1 0 0
12-16 0 0 0 0
18 2 2 0 0
20 1 1 0 0
22 3 3 0 0
24 1 0 0 0
26 100 96 0 0
28 52 34 2 1
30 202 139 1 0
32 304 28 0 0

Hypohamiltonian snarks

Lists of hypohamiltonian snarks can be found on the snarks page.

References

[1] R. Aldred, B. McKay and N. Wormald, Small hypohamiltonian graphs, Journal of Combinatorial Mathematics and Combinatorial Computing 23:143-152, 1997.
[2] J. Goedgebeur and C.T. Zamfirescu, Improved bounds for hypohamiltonian graphs, Ars Mathematica Contemporanea, 13(2):235-257, 2017.