# Almost hypohamiltonian graphs

A graph G is *hypohamiltonian* if G is non-hamiltonian and G-v is hamiltonian for every vertex v of G.
A graph G is *almost hypohamiltonian* if G is non-hamiltonian and there exists a vertex w of G such that G-w is non-hamiltonian and G-v is hamiltonian for every vertex v of G different from w.

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

The following lists are available:

Lists of hypohamiltonian graphs can be found here.

The counts of incomplete cases are indicated with a '≥' in the table.
In all other cases the numbers are the counts of the complete sets of almost hypohamiltonian graphs.

### Almost hypohamiltonian graphs

All results were obtained with the program GenHypohamiltonian of Goedgebeur and Zamfirescu [1].

The following table gives the complete lists of all almost hypohamiltonian graphs with a given lower bound on the girth.

Vertices |
girth ≥ 3 |
girth ≥ 4 |
girth ≥ 5 |
girth ≥ 6 |

0-16 |
0 |
0 |
0 |
0 |

17 |
2 |
2 |
2 |
0 |

18 |
2 |
2 |
1 |
0 |

19 |
? |
27 |
4 |
0 |

20 |
? |
? |
14 |
0 |

21 |
? |
? |
27 |
0 |

22 |
? |
? |
133 |
0 |

23 |
? |
? |
404 |
0 |

24 |
? |
? |
≥68 |
0 |

25-26 |
? |
? |
? |
0 |

### Cubic almost 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 almost hypohamiltonicity as a filter.

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

Vertices |
girth ≥ 4 |
girth ≥ 5 |
girth ≥ 6 |

0-24 |
0 |
0 |
0 |

26 |
10 |
10 |
0 |

28 |
6 |
2 |
0 |

30 |
25 |
12 |
0 |

32 |
74 |
4 |
0 |

## References

[1] J. Goedgebeur and C.T. Zamfirescu, On almost hypohamiltonian graphs, submitted, 2017. Preprint: arXiv:1606.06577