×

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

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)
PDF BibTeX XML Cite
Full Text: DOI arXiv

References:

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.