﻿ Planar Hypohamiltonian Graphs Data | Reza Jooyandeh

Planar Hypohamiltonian Graphs Data

Planar Hypohamiltonian Graphs
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.
40 Vertices
 Graph File Face Sequence Degree Sequence Count 05x04, 22x05 30x03, 10x04 4 684B 05x04, 22x05 31x03, 08x04, 01x05 10 1.66KB 05x04, 22x05 32x03, 06x04, 02x05 9 1.50KB 05x04, 22x05 33x03, 04x04, 03x05 2 342B 25 4.17KB
42 Vertices
 Graph File Face Sequence Degree Sequence Count 01x04, 26x05 34x03, 08x04 5 885B 01x04, 26x05 35x03, 06x04, 03x05 2 354B 07x04, 22x05 30x03, 102x04 4 724B 07x04, 22x05 31x03, 10x04, 01x05 28 4.94KB 07x04, 22x05 32x03, 08x04, 02x05 57 10.0KB 07x04, 22x05 33x03, 06x04, 03x05 49 8.66KB 07x04, 22x05 33x03, 07x04, 01x05, 01x06 11 1.94KB 07x04, 22x05 34x03, 04x04, 04x05 10 1.76KB 07x04, 22x05 34x03, 05x04, 02x05, 01x06 5 905B 07x04, 22x05 34x03, 06x04, 02x06 6 1.06KB 07x04, 22x05 35x03, 04x04, 01x05, 02x06 2 362B 179 31.6KB
43 Vertices
 Graph File Face Sequence Degree Sequence Count 04x04, 203x05, 01x7 36x03, 06x04, 01x06 1 182B 04x04, 203x05, 01x7 37x03, 04x04, 01x05, 01x06 1 182B 05x04, 22x05, 01x8 34x03, 09x04 8 1.42KB 05x04, 22x05, 01x8 35x03, 07x04, 01x05 20 3.55KB 05x04, 22x05, 01x8 36x03, 05x04, 02x05 19 3.37KB 05x04, 22x05, 01x8 37x03, 03x04, 03x05 1 182B 05x04, 22x05, 01x8 37x03, 04x04, 01x05, 01x06 1 182B 05x04, 24x05 32x03, 101x04 52 9.34KB 05x04, 24x05 33x03, 09x04, 01x05 148 26.5KB 05x04, 24x05 34x03, 07x04, 02x05 175 31.4KB 05x04, 24x05 34x03, 08x04, 01x06 2 368B 05x04, 24x05 35x03, 05x04, 03x05 56 10.0KB 05x04, 24x05 35x03, 06x04, 01x05, 01x06 6 1.07KB 05x04, 24x05 36x03, 03x04, 04x05 1 184B 05x04, 24x05 36x03, 04x04, 02x05, 01x06 4 736B 05x04, 24x05 37x03, 02x04, 03x05, 01x06 1 184B 05x04, 24x05 37x03, 03x04, 01x05, 02x06 1 184B 497 89.2KB
Previously Known Ones
 Graph File Author(s) Vertex Count Face Sequence Degree Sequence G. Wiener & M. Araya [2] 42 1x4, 26x5 34x3, 8x4 177B C. T. Zamfirescu & T. Zamfirescu [3] 48 1x4, 28x5, 1x8 40x3, 8x4 201B W. Hatzel [4] 57 1x4, 28x5, 4x8 52x3, 5x4 234B C. Thomassen [5] 105 66x5, 1x10 85x3, 15x4, 5x5 446B
Example on 40 Vertices
JavaScript must be enabled to display this example.