On almost hypohamiltonian graphs. (English) Zbl 1417.05114

Goedgebeur, Jan; Zamfirescu, Carol T.

Discrete Math. Theor. Comput. Sci. 21, No. 4, Paper No. 5, 18 p. (2019).

Summary: A graph \(G\) is almost hypohamiltonian (a.h.) if \(G\) is non-Hamiltonian, there exists a vertex \(w\) in \(G\) such that \(G-w\) is non-Hamiltonian, and \(G-v\) is Hamiltonian for every vertex \(v\ne w\) in \(G\). The second author asked in [J. Graph Theory 79, No. 1, 63–81 (2015; Zbl 1312.05076)] for all orders for which a.h. graphs exist. Here we solve this problem. To this end, we present a specialised algorithm which generates complete sets of a.h. graphs for various orders. Furthermore, we show that the smallest cubic a.h. graphs have order 26. We provide a lower bound for the order of the smallest planar a.h. graph and improve the upper bound for the order of the smallest planar a.h. graph containing a cubic vertex. We also determine the smallest planar a.h. graphs of girth 5, both in the general and cubic case. Finally, we extend a result of E. Steffen [Discrete Math. 188, No. 1–3, 183–203 (1998; Zbl 0956.05089)] on snarks and improve two bounds on longest paths and longest cycles in polyhedral graphs due to M. Jooyandeh et al. [J. Graph Theory 84, No. 2, 121–133 (2017; Zbl 1356.05029)].

MSC:

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

Keywords:

Hamiltonian graph; hypo-Hamiltonian graph; almost hypo-Hamiltonian graph; planar graph; cubic graph; exhaustive generation

Citations:

Zbl 1312.05076; Zbl 0956.05089; Zbl 1356.05029