K-2-Hamiltonian graphs : I

Motivated by a conjecture of Grunbaum 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

Publication year:2021

Accessibility:Open