Academic Bibliography

 Search 200 years of publications by Ghent University researchers.
Advanced search
1 file | 479.54 KB
Add to list
  1. Search results
  2. K-2-Hamiltonian graphs : I

K-2-Hamiltonian graphs : I

Carol Zamfirescu (UGent)
(2021) SIAM JOURNAL ON DISCRETE MATHEMATICS. 35(3). p.1706-1728
Author
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

  • Download
    CTZamfirescu-45.pdf
    • full text (Accepted manuscript)
    • |
    • open access
    • |
    • PDF
    • |
    • 479.54 KB

Citation

Please use this url to cite or link to this publication:

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: