$K_2$-Hamiltonian Graphs: I
Carol T. Zamfirescu · SIAM Journal on Discrete Mathematics · 2021
Motivated by a conjecture of Grünbaum and a problem of Katona, Kostochka, Pach, and Stechkin, both dealing with non-Hamiltonian $n$-vertex graphs and their $(n-2)$-cycles, we investigate $K_2$- Hamiltonian graphs, i.e., graphs in which the removal of any pair of adjacent vertices yields a Hamiltonian graph. In this first part, we prove structural properties and show that there exist infinitely many cubic non-Hamiltonian $K_2$-Hamiltonian graphs, both of the 3-edge-colorable and the non-3-edge-colorable variety. In fact, cubic $K_2$-Hamiltonian graphs with chromatic index 4 (such as Petersen's graph) are a subset of the critical snarks. On the other hand, it is proven that non-Hamiltonian $K_2$-Hamiltonian graphs of any maximum degree exist. Several operations conserving $K_2$-Hamiltonicity are described, one of which leads to the result that there exists an infinite family of non-Hamiltonian $K_2$-Hamiltonian graphs in which, asymptotically, a quarter of vertices has the property that removing such a vertex yields a non-Hamiltonian graph. We extend a celebrated result of Tutte by showing that every planar $K_2$-Hamiltonian graph with minimum degree at least 4 is Hamiltonian. Finally, we investigate $K_2$-traceable graphs and discuss open problems.