Planar Hypohamiltonian Graphs on 40 Vertices

• Published in 2013
• Added on 2019-05-09

A graph is hypohamiltonian if it is not Hamiltonian, but the deletion of any single vertex gives a Hamiltonian graph. Until now, the smallest known planar hypohamiltonian graph had 42 vertices, a result due to Araya and Wiener. That result is here improved upon by 25 planar hypohamiltonian graphs of order 40, which are found through computer-aided generation of certain families of planar graphs with girth 4 and a fixed number of 4-faces. It is further shown that planar hypohamiltonian graphs exist for all orders greater than or equal to 42. If Hamiltonian cycles are replaced by Hamiltonian paths throughout the definition of hypohamiltonian graphs, we get the definition of hypotraceable graphs. It is shown that there is a planar hypotraceable graph of order 154 and of all orders greater than or equal to 156. We also show that the smallest hypohamiltonian planar graph of girth 5 has 45 vertices.

Links

• http://arxiv.org/abs/1302.2698v4
• http://arxiv.org/pdf/1302.2698v4

Other information

BibTeX entry

@article{PlanarHypohamiltonianGraphson40Vertices,
	key = {PlanarHypohamiltonianGraphson40Vertices},
	type = {article},
	title = {Planar Hypohamiltonian Graphs on 40 Vertices},
	author = {Mohammadreza Jooyandeh and Brendan D. McKay and Patric R. J. {\"{O}}sterg{\aa}rd and Ville H. Pettersson and Carol T. Zamfirescu},
	abstract = {A graph is hypohamiltonian if it is not Hamiltonian, but the deletion of any
single vertex gives a Hamiltonian graph. Until now, the smallest known planar
hypohamiltonian graph had 42 vertices, a result due to Araya and Wiener. That
result is here improved upon by 25 planar hypohamiltonian graphs of order 40,
which are found through computer-aided generation of certain families of planar
graphs with girth 4 and a fixed number of 4-faces. It is further shown that
planar hypohamiltonian graphs exist for all orders greater than or equal to 42.
If Hamiltonian cycles are replaced by Hamiltonian paths throughout the
definition of hypohamiltonian graphs, we get the definition of hypotraceable
graphs. It is shown that there is a planar hypotraceable graph of order 154 and
of all orders greater than or equal to 156. We also show that the smallest
hypohamiltonian planar graph of girth 5 has 45 vertices.},
	comment = {},
	date_added = {2019-05-09},
	date_published = {2013-12-07},
	urls = {http://arxiv.org/abs/1302.2698v4,http://arxiv.org/pdf/1302.2698v4},
	collections = {Fun maths facts},
	url = {http://arxiv.org/abs/1302.2698v4 http://arxiv.org/pdf/1302.2698v4},
	year = 2013,
	urldate = {2019-05-09},
	archivePrefix = {arXiv},
	eprint = {1302.2698},
	primaryClass = {math.CO}
}