On hypohamiltonian snarks and a theorem of Fiorini. (English) Zbl 1395.05044

Goedgebeur, Jan; Zamfirescu, Carol T.

Ars Math. Contemp. 14, No. 2, 227-249 (2018).

Summary: In [Acta Appl. Math. 76, No. 1, 57–88 (2003; Zbl 1018.05033)], A. Cavicchioli et al. corrected an omission in the statement and proof of S. Fiorini’s theorem on hypohamiltonian snarks [in: Graphs and other combinatorial topics. Proceedings of the Third Czechoslovak Symposium on Graph Theory, held in Prague, August 24th to 27th, 1982. Leipzig: BSB B. G. Teubner Verlagsgesellschaft. 70–75 (1983; Zbl 0535.05045)]. However, their version of this theorem contains an unattainable condition for certain cases. We discuss and extend the results of Fiorini [loc. cit.] and Cavicchioli et al. [loc. cit.] and present a version of this theorem which is more general in several ways. Using Fiorini’s erroneous result, E. Steffen [Math. Slovaca 51, No. 2, 141–150 (2001; Zbl 0985.05022)] showed that hypohamiltonian snarks exist for some orders \(n\geq10\) and each even \(n\geq 92\). We rectify Steffen’s [loc. cit.] proof by providing a correct demonstration of a technical lemma on flower snarks, which might be of separate interest. We then strengthen Steffen’s theorem [loc. cit.] to the strongest possible form by determining all orders for which hypohamiltonian snarks exist. This also strengthens a result of E. Máčajová and M. Škoviera [Discrete Math. 306, No. 8–9, 779–791 (2006; Zbl 1092.05026)]. Finally, we verify a conjecture of E. Steffen on hypohamiltonian snarks up to 36 vertices [J. Graph Theory 78, No. 3, 195–206 (2015; Zbl 1309.05108)].

MSC:

05C10	Planar graphs; geometric and topological aspects of graph theory
05C38	Paths and cycles
05C45	Eulerian and Hamiltonian graphs
05C85	Graph algorithms (graph-theoretic aspects)

Keywords:

hypo-Hamiltonian snark; irreducible snark; dot product

Citations:

Zbl 1018.05033; Zbl 0535.05045; Zbl 0985.05022; Zbl 1092.05026; Zbl 1309.05108

References: