Hypohamiltonian snarks. (English) Zbl 0535.05045

Graphs and other combinatorial topics, Proc. 3rd Czech. Symp., Prague 1982, Teubner-Texte Math. 59, 70-75 (1983).
[For the entire collection see Zbl 0517.00002.]
A graph G is hypohamiltonian if G is not Hamiltonian but G-v is Hamiltonian for all \(v\in V(G)\). A snark is a cyclically 4-edge connected cubic graph with girth at least 5 that is not Tait-colorable (and thus non-Hamiltonian). The author shows that R. Isaacs’ flower snarks [Am. Math. Mon. 82, 221-239 (1975; Zbl 0311.05109)] are hypohamiltonian but that Isaacs’ construction for generating a snark from two smaller snarks produces a hypohamiltonian snark from two smaller hypohamiltonian snarks only under special conditions. He states that the M. K. Gol’dberg [J. Comb. Theory, Ser. B 31, 282-291 (1981; Zbl 0449.05037)] are not hypohamiltonian and relays Chetwynd’s result that the double-star snark of Isaacs on 30 vertices is hypohamiltonian.
Misprints in the paths P sequences on page 72 should be corrected as follows. \(F_{4j+3}-a_ 5:\) change the first \(a_ 6\) to \(a_ 7\), the second \(c_ 7\) to \(c_ 6\) and d to \(d_ 7\). \(F_{4j+3}-c_ 3:\) transpose \(d_ 2\) and \(b_ 2\). \(F_{4j+1}-c_ 3:\) change the first \(a_ 3\) to \(d_ 3\).
Reviewer: R.Entringer


05C45 Eulerian and Hamiltonian graphs