Planar
hypohamiltonian graphs are the family of
planar
graphs that are not
Hamiltonian, but removing any of the vertecies makes them Hamiltonian. This page contains the list of smallest
known planar hypohamiltonian graphs.
All of graphs of order 40, 42 and 43 are from
[1] although one of the graphs on 42 were found previously in
[2].
The ones of order 48, 57 and 105 are from
[3],
[4] and
[5]; respectively.
The graph
format is
planar code. A complete definition can be found in the
plantri
manual (Appendix A). For the graphs on this page, the following should be adequate. Each graph is given as a sequence of bytes, starting with a byte containing the number of vertices. Then for each vertex, a list of the neighbours is given, one neighbour per byte in clockwise order, plus a zero byte to end the list. Vertices are numbered starting with 1. A graph with n vertices and e edges thus occupies exactly
1+2e+n bytes.
Reference:
[1] M. Jooyandeh,
B.D. McKay,
P.R.J. Östergård, V. Pettersson,
C.T. Zamfirescu,
Planar Hypohamiltonian Graphs on 40 Vertices,
J. Graph Theory,
Avaliable on arXiv.org,
PDF.
[2] G. Wiener and M. Araya,
On planar hypohamiltonian graphs,
J. Graph Theory,
67 (2011) 55-68.
[3] C.T. Zamfirescu and T.I. Zamfirescu, A Planar
Hypohamiltonian Graph with 48 Vertices,
J. Graph Theory 55(4) (2007)
338-342.
[4] W. Hatzel, Ein planarer hypohamiltonscher Graph mit 57 Knoten,
Math. Ann.,
243 (1979) 213-236 (in German).
[5] C. Thomassen, Planar and
infinite hypohamiltonian and hypotraceable Graphs,
Discrete Math.,
14
(1976) 377-389.