Paper Info
Title
K-2-Hamiltonian Graphs: I
Abstract
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
Year
DOI
Venue
2021
10.1137/20M1355252
SIAM JOURNAL ON DISCRETE MATHEMATICS
Keywords
DocType
Volume
Hamiltonian cycle, snark, vertex-deleted subgraph, hypohamiltonian, planar
Journal
35
Issue
ISSN
Citations 
3
0895-4801
0
PageRank 
References 
Authors
0.34
0
1
Name
Order
Citations
PageRank
Carol T. Zamfirescu13815.25