On this page we give some classes of graphs imbedded in the plane. We focus on graph classes that are not so easy to generate using plantri.
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.
12 vertices: 1
14 vertices: 0
16 vertices: 1
18 vertices: 1
20 vertices: 6
22 vertices: 14
24 vertices: 98
26 vertices: 529
28 vertices: 4035
30 vertices: 31009
32 vertices: 252386
34 vertices: 2073769 (bzip2)
36 vertices: 17277113 (bzip2; 395MB)
In this section we give some families of nonhamiltonian planar cubic graphs defined according to some properties. All the graphs are simple, 3-connected, cubic, planar and nonhamiltonian; we list any further defining properties in the heading. For each graph family, there are no smaller graphs than we give.
38 vertices: 6
40 vertices: 37
42 vertices: 277
44 vertices: 1732
46 vertices: 11204
48 vertices: 70614
42 vertices: 3
44 vertices: 3
46 vertices: 19
48 vertices: 30
50 vertices: 126
44 vertices: 1
46 vertices: 3
48 vertices: 1
50 vertices: 3
52 vertices: 6
54 vertices: 12
56 vertices: 49
58 vertices: 126
60 vertices: 214
62 vertices: 659
64 vertices: 1467
66 vertices: 3247
68 vertices: 9187
70 vertices: 22069
72 vertices: 50514
74 vertices: 137787
76 vertices: 339804 (bzip2)
44 vertices: 1
46 vertices: 1
48 vertices: 0
50 vertices: 3
52 vertices: 6
54 vertices: 2
56 vertices: 22
58 vertices: 37
60 vertices: 31
62 vertices: 194
64 vertices: 298
66 vertices: 306
68 vertices: 1538
70 vertices: 2566
72 vertices: 3091
74 vertices: 13487
A graph is hypohamiltonian if it is not hamiltonian but becomes hamiltonian if any vertex is removed. Here are some examples of hypohamiltonian graphs which are planar.
The smallest known cubic planar hypohamiltonian graphs have 70 vertices. The first was found by Araya and Wiener, while six more were found by Mohammadreza Jooyandeh and myself. These graphs have girth 4, which is the smallest possible girth for a cubic hypohamiltonian graph. One of the new graphs, with a structure somewhat different from the rest, appears below. It is not known if these graphs are the smallest.
70 vertices: 7
We have proved that the smallest cubic planar hypohamiltonian graphs of girth 5 (the largest possible girth for a cubic planar graph) have 76 vertices. There are three of them.
76 vertices: 3
An a-edge in a graph is an edge which is present on every hamiltonian cycle. We exclude the case of non-hamiltonian graphs. For a 3-connected cubic graph, it is easy to see what happens when a triangle is reduced to a point, so we exclude that case too.
In the following files are all cubic planar 3-connected hamiltonian graphs with no 3-cycle (which is equivalent to no 3-face) that have at least one a-edge, up to 38 vertices.
Page Master: Brendan McKay, brendan.mckay@anu.edu.au