K2-Hamiltonian graphs: II

In this paper, we use theoretical and computational tools to continue our investigation of (Formula presented.) -hamiltonian graphs, that is, graphs in which the removal of any pair of adjacent vertices yields a hamiltonian graph, and their interplay with (Formula presented.) -hamiltonian graphs, that is, graphs in which every vertex-deleted subgraph is hamiltonian. Perhaps surprisingly, there exist graphs that are both (Formula presented.) - and (Formula presented.) -hamiltonian, yet non-hamiltonian, for example, the Petersen graph. Grünbaum conjectured that every planar (Formula presented.) -hamiltonian graph must itself be hamiltonian; Thomassen disproved this conjecture. Here we show that even planar graphs that are both (Formula presented.) - and (Formula presented.) -hamiltonian need not be hamiltonian, and that the number of such graphs grows at least exponentially. Motivated by results of Aldred, McKay, and Wormald, we determine for every integer (Formula presented.) that is not 14 or 17 whether there exists a (Formula presented.) -hypohamiltonian, that is non-hamiltonian and (Formula presented.) -hamiltonian, graph of order (Formula presented.), and characterise all orders for which such cubic graphs and such snarks exist. We also describe the smallest cubic planar graph which is (Formula presented.) -hypohamiltonian, as well as the smallest planar (Formula presented.) -hypohamiltonian graph of girth 5. We conclude with open problems and by correcting two inaccuracies from the first article.