On cubic planar hypohamiltonian and hypotraceable graphs. (English) Zbl 1217.05065

Araya, Makoto; Wiener, Gábor

Electron. J. Comb. 18, No. 1, Research Paper P85, 11 p. (2011).

Summary: We present a cubic planar hypohamiltonian graph on 70 vertices, improving the best known bound of 94 by Thomassen and derive some consequences concerning longest paths and cycles of planar 3-connected graphs. We also show that cubic planar hypohamiltonian graphs on \(n\) vertices exist for every even number \(n \geq 86\) and that cubic planar hypotraceable graphs exist on \(n\) vertices for every even number \(n \geq 356\), settling an open question of Holton and Sheehan.

MSC:

05C10	Planar graphs; geometric and topological aspects of graph theory
05C38	Paths and cycles
05C45	Eulerian and Hamiltonian graphs