A K2-hypohamiltonian graph is a non-hamiltonian graph in which the removal of any pair of adjacent vertices yields a hamiltonian graph.
The graph lists are currently only available in 'graph6' format.
The following lists are available:
Lists of hypohamiltonian graphs can be found here.
The following table gives the complete lists of all K2-hypohamiltonian graphs with a given lower bound on the girth.
All results were obtained with the program GenK2Hypohamiltonian , see [1,2] for details.
Vertices | Girth ≥ 3 | Girth ≥ 4 | Girth ≥ 5 | Girth ≥ 6 | Girth ≥ 7 |
---|---|---|---|---|---|
10 | 1 | 1 | 1 | 0 | 0 |
11 | 0 | 0 | 0 | 0 | 0 |
12 | 0 | 0 | 0 | 0 | 0 |
13 | 1 | 1 | 1 | 0 | 0 |
14 | 0 | 0 | 0 | 0 | 0 |
15 | 1 | 1 | 1 | 0 | 0 |
16 | 4 | 4 | 4 | 0 | 0 |
17 | 0 | 0 | 0 | 0 | 0 |
18 | 3 | 3 | 3 | 0 | 0 |
19 | 28 | 28 | 28 | 0 | 0 |
20 | ? | 2 | 2 | 0 | 0 |
21 | ? | ? | 31 | 0 | 0 |
22 | ? | ? | 332 | 0 | 0 |
23 | ? | ? | 19 | 0 | 0 |
24 | ? | ? | 613 | 0 | 0 |
25 | ? | ? | ? | 1 | 0 |
26 | ? | ? | ? | 0 | 0 |
27 | ? | ? | ? | 0 | 0 |
28-30 | ? | ? | ? | ? | 0 |
Lists of K2-hypohamiltonian snarks can be found on the snarks page.
[1] J. Goedgebeur, J. Renders, G. Wiener and C.T. Zamfirescu, K2-Hamiltonian Graphs: II, manuscript.
[2] J. Goedgebeur, J. Renders, and C.T. Zamfirescu, Generation and new infinite families of K2-hypohamiltonian graphs, manuscript.