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

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
Full Text: