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