TOPICS

# Planar Hypohamiltonian Graph

A planar hypohamiltonian graph is a hypohamiltonian graph that is also planar. A number of planar hypohamiltonian graphs are illustrated above.

Chvátal (1973) first asked if there existed planar hypohamiltonian graphs, and in fact it was conjectured that such graphs might not exist (Grünbaum 1974, Jooyandeh et al. 2017). An infinite family was subsequently found by Thomassen (1976), the smallest among them having 105 vertices. The following table summarizes incrementally smallest known planar hypohamiltonian graphs.

 vertex count graph reference(s) 94 94-Thomassen graphs 57 Hatzel graph Hatzel (1979) 48 48-Zamfirescu graph Zamfirescu and Zamfirescu (2007) 42 Wiener-Araya graph Wiener and Araya (2009) 42 179 graphs Jooyandeh et al. (2017) 40 25 graphs Jooyandeh et al. (2017) 38 2 graphs Tsai (2024) 37 6 graphs Tsai (2024) 34 2 graphs Tsai (2024)

Jooyandeh et al. (2017) searched for "planar 4-face deflatable hypohamiltonian graphs" and found 25 on 40 vertices (all of girth 4), 179 on 42 graphs (including the Wiener-Araya graph), and 496 on 43 vertices. They also showed that there exist planar hypohamiltonian graphs of order for every (Jooyandeh et al. 2017), a result subsequently improved to (Tsai 2024). It is not known if 34 is the smallest possible vertex count of a planar hypohamiltonian, with 23 being the best currently known lower bound (Goedgebeur and Zamfirescu 2017; improving previous bounds from Aldred et al. 1997, Jooyandeh et al. 2017).

There are no hypohamiltonian planar graphs with girth 5 on fewer than 45 vertices, and there is exactly one such graph on 45 vertices (Jooyandeh et al. 2017), illustrated above.

Every planar hypohamiltonian graph contains a vertex of degree 3 (Thomassen 1978), and letting be the vertex connectivity, the minimum vertex degree, and the edge connectivity of a planar hypohamiltonian graph ,

(Jooyandeh et al. 2017). Furthermore, a planar hypohamiltonian graph can have girth at most 5 (Jooyandeh et al. 2017).

A number of cubic planar hypohamiltonian graphs have been found by Araya and Wiener (2011), McKay and Jooyandeh (McKay), and Tsai (2024).

Cubic Planar Hypohamiltonian Graph, Hatzel Graph, Hypohamiltonian Graph, Planar Graph, Planar Hypotraceable Graph, Thomassen Graphs, Wiener-Araya Graph, Zamfirescu Graphs

## Explore with Wolfram|Alpha

More things to try:

## References

Aldred, R. E. L.; Bau, S.; Holton, D. A.; and McKay, B. D. "Nonhamiltonian 3-Connected Cubic Planar Graphs." SIAM J. Disc. Math. 13, 25-32, 2000.Aldred, R. E. L.; McKay, B. D.; and Wormald, N. C. "Small Hypohamiltonian Graphs." J. Combin. Math. Combin. Comput. 23, 143-152, 1997.Araya, M. and Wiener, G. "On Cubic Planar Hypohamiltonian and Hypotraceable Graphs." Elec. J. Combin. 18, 2011. http://www.combinatorics.org/ojs/index.php/eljc/article/view/v18i1p85/.Chvátal, V. "Flip-Flops in Hypohamiltonian Graphs." Canad. Math. Bull. 16, 33-41, 1973.Goedgebeur, J. and Zamfirescu, C. T. "Improved Bounds for Hypohamiltonian Graphs." Ars Math. Contemp. 13, 235-257, 2017.Gruünbaum, B. "Vertices Missed by Longest Paths or Circuits." J. Combin. Th. 17, 31-38, 1974.Holton, D. A. and Sheehan, J. The Petersen Graph. Cambridge, England: Cambridge University Press, 1993.Jooyandeh, M.; McKay, B. D.; Östergård, P. R. J.; Pettersson, V. H.; and Zamfirescu, C. T. "Planar Hypohamiltonian Graphs on 40 Vertices." J. Graph Th. 84, 121-133, 2017.McKay, B. D. "Plane Graphs: Hypohamiltonian Planar Graphs." http://users.cecs.anu.edu.au/~bdm/data/planegraphs.html.Thomassen, C. "Hypohamiltonian and Hypotraceable Graphs." Disc. Math. 9, 91-96, 1974.Thomassen, C. "On Hypohamiltonian Graphs." Disc. Math. 10, 383-390, 1974.Thomassen, C. "Planar and Infinite Hypohamiltonian and Hypotraceable Graphs." Disc. Math 14, 377-389, 1976.Thomassen, C. "Hypohamiltonian Graphs and Digraphs." In Theory and Applications of Graphs Proceedings, Michigan May 11-15, 1976 (Ed. Y. Alavi and D. R. Lick). New York: Springer-Verlag, pp. 557-571, 1978.Thomassen, C. "Planar Cubic Hypohamiltonian and Hypotraceable Graphs." J. Comb. Th. B 30, 36-44, 1981.Tsai, C.-C. "Small Planar Hypohamiltonian Graphs." 8 Apr 2024. https://arxiv.org/abs/2403.18384.Wiener, G. and Araya, M. "The Ultimate Question." 20 Apr 2009. http://arxiv.org/abs/0904.3012.Wiener, G. and Araya, M. "On Planar Hypohamiltonian Graphs." J. Graph Th. 67, 55-68, 2011.Zamfirescu, C. T. and Zamfirescu, T. I. "A Planar Hypohamiltonian Graph with 48 Vertices." J. Graph Th. 48, 338-342, 2007.

## Cite this as:

Weisstein, Eric W. "Planar Hypohamiltonian Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/PlanarHypohamiltonianGraph.html