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.

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, arXiv preprint: arXiv:1602.07171, 2016.