Platypus graphs

A platypus graph is a non-hamiltonian graph for which every vertex-deleted subgraph is traceable (i.e. contains a hamiltonian path).

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

Platypus graphs

All results were obtained with the program GenHypohamiltonian, see [1] for details.

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

Vertices girth ≥ 3 girth ≥ 4 girth ≥ 5 girth ≥ 6 girth ≥ 7 girth ≥ 8 girth ≥ 9
0-8 0 0 0 0 0 0 0
9 4 0 0 0 0 0 0
10 48 2 2 0 0 0 0
11 814 4 3 0 0 0 0
12 24847 48 7 1 0 0 0
13 ? 319 27 1 0 0 0
14 ? 6623 161 2 0 0 0
15 ? ? 934 1 0 0 0
16 ? ? 7674 9 1 0 0
17 ? ? 82240 53 0 0 0
18 ? ? ? 277 0 0 0
19 ? ? ? 1161 0 0 0
20 ? ? ? 7659 5 0 0
21 ? ? ? ? 35 0 0
22 ? ? ? ? ? 1 0
23 ? ? ? ? ? 1 0
24 ? ? ? ? ? 5 0

References

[1] J. Goedgebeur, A. Neyt and C.T. Zamfirescu, Structural and computational results on platypus graphs, submitted, 2017. Preprint: arXiv:1712.05158