# 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, Discrete Mathematics and Theoretical Computer Science, 21(4), 18 pages, 2019.