- Author
- Carol Zamfirescu (UGent)
- Organization
- 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
- Keywords
- Hamiltonian cycle, snark, vertex-deleted subgraph, hypohamiltonian, planar, INFINITE FAMILIES, HYPOHAMILTONIAN GRAPHS, PLANAR, CONSTRUCTIONS, PATHS
Downloads
-
CTZamfirescu-45.pdf
- full text (Accepted manuscript)
- |
- open access
- |
- |
- 479.54 KB
Citation
Please use this url to cite or link to this publication: http://hdl.handle.net/1854/LU-8724976
- MLA
- Zamfirescu, Carol. “K-2-Hamiltonian Graphs : I.” SIAM JOURNAL ON DISCRETE MATHEMATICS, vol. 35, no. 3, 2021, pp. 1706–28, doi:10.1137/20M1355252.
- APA
- Zamfirescu, C. (2021). K-2-Hamiltonian graphs : I. SIAM JOURNAL ON DISCRETE MATHEMATICS, 35(3), 1706–1728. https://doi.org/10.1137/20M1355252
- Chicago author-date
- Zamfirescu, Carol. 2021. “K-2-Hamiltonian Graphs : I.” SIAM JOURNAL ON DISCRETE MATHEMATICS 35 (3): 1706–28. https://doi.org/10.1137/20M1355252.
- Chicago author-date (all authors)
- Zamfirescu, Carol. 2021. “K-2-Hamiltonian Graphs : I.” SIAM JOURNAL ON DISCRETE MATHEMATICS 35 (3): 1706–1728. doi:10.1137/20M1355252.
- Vancouver
- 1.Zamfirescu C. K-2-Hamiltonian graphs : I. SIAM JOURNAL ON DISCRETE MATHEMATICS. 2021;35(3):1706–28.
- IEEE
- [1]C. Zamfirescu, “K-2-Hamiltonian graphs : I,” SIAM JOURNAL ON DISCRETE MATHEMATICS, vol. 35, no. 3, pp. 1706–1728, 2021.
@article{8724976, 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}}, author = {{Zamfirescu, Carol}}, issn = {{0895-4801}}, journal = {{SIAM JOURNAL ON DISCRETE MATHEMATICS}}, keywords = {{Hamiltonian cycle,snark,vertex-deleted subgraph,hypohamiltonian,planar,INFINITE FAMILIES,HYPOHAMILTONIAN GRAPHS,PLANAR,CONSTRUCTIONS,PATHS}}, language = {{eng}}, number = {{3}}, pages = {{1706--1728}}, title = {{K-2-Hamiltonian graphs : I}}, url = {{http://doi.org/10.1137/20M1355252}}, volume = {{35}}, year = {{2021}}, }
- Altmetric
- View in Altmetric
- Web of Science
- Times cited: