Infinitely many planar cubic hypohamiltonian graphs of girth 5. (English) Zbl 1391.05153

Goedgebeur, Jan; Zamfirescu, Carol T.

J. Graph Theory 88, No. 1, 40-45 (2018).

Summary: A graph \(G\) is hypohamiltonian if \(G\) is non-Hamiltonian and for every vertex \(v\) in \(G\), the graph \(G-v\) is Hamiltonian. B. D. McKay [J. Graph Theory 85, No. 1, 7–11 (2017; Zbl 1365.05064)] asked whether infinitely many planar cubic hypohamiltonian graphs of girth 5 exist. We settle this question affirmatively.

MSC:

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

Keywords:

cubic; dot product; Hamiltonian graph; hypo-Hamiltonian graph

Citations:

Zbl 1365.05064