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 and lists of K2-hypohamiltonian graphs can be found here.
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 |
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 |
Lists of hypohamiltonian snarks can be found on the snarks page.
[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.