Academic Bibliography

 Search 200 years of publications by Ghent University researchers.
Advanced search
2 files | 1.09 MB
Add to list
  1. Search results
  2. Few hamiltonian cycles in graphs with...

Few hamiltonian cycles in graphs with one or two vertex degrees

Jan Goedgebeur (UGent) , Jorik Jooken, On-Hei Solomon Lo, Ben Seamone and Carol Zamfirescu (UGent)
(2024) MATHEMATICS OF COMPUTATION. 93(350). p.3059-3082
Author
Organization
Project
Abstract
Inspired by Sheehan's conjecture that no 4 -regular graph contains exactly one hamiltonian cycle, we prove results on hamiltonian cycles in regular graphs and nearly regular graphs. We fully disprove a conjecture of Haythorpe on the minimum number of hamiltonian cycles in regular hamiltonian graphs, thereby extending a result of Zamfirescu, as well as correct and complement Haythorpe's computational enumerative results from [Exp. Math. 27 (2018), no. 4, 426-430]. Thereafter, we use the Lov<acute accent>asz Local Lemma to extend Thomassen's independent dominating set method. This extension allows us to find a second hamiltonian cycle that inherits linearly many edges from the first hamiltonian cycle. Regarding the limitations of this method, we answer a question of Haxell, Seamone, and Verstraete, and settle the first open case of a problem of Thomassen by showing that for k is an element of {5, 6} there exist infinitely many k -regular hamiltonian graphs having no independent dominating set with respect to a prescribed hamiltonian cycle. Motivated by an observation of Aldred and Thomassen, we prove that for every kappa is an element of {2, 3} and any positive integer k, there are infinitely many non -regular graphs of connectivity kappa containing exactly one hamiltonian cycle and in which every vertex has degree 3 or 2k.
Keywords
INDEPENDENT DOMINATING SETS, REGULAR GRAPHS, Hamiltonian cycle, regular graph, Lovasz Local Lemma

Downloads

  • Download
    230203-OnHeiSolomonLo-v3.pdf
    • full text (Accepted manuscript)
    • |
    • open access
    • |
    • PDF
    • |
    • 764.20 KB
  • Download
    (...).pdf
    • full text (Published version)
    • |
    • UGent only
    • |
    • PDF
    • |
    • 322.72 KB

Citation

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

MLA
Goedgebeur, Jan, et al. “Few Hamiltonian Cycles in Graphs with One or Two Vertex Degrees.” MATHEMATICS OF COMPUTATION, vol. 93, no. 350, 2024, pp. 3059–82, doi:10.1090/mcom/3943.
APA
Goedgebeur, J., Jooken, J., Lo, O.-H. S., Seamone, B., & Zamfirescu, C. (2024). Few hamiltonian cycles in graphs with one or two vertex degrees. MATHEMATICS OF COMPUTATION, 93(350), 3059–3082. https://doi.org/10.1090/mcom/3943
Chicago author-date
Goedgebeur, Jan, Jorik Jooken, On-Hei Solomon Lo, Ben Seamone, and Carol Zamfirescu. 2024. “Few Hamiltonian Cycles in Graphs with One or Two Vertex Degrees.” MATHEMATICS OF COMPUTATION 93 (350): 3059–82. https://doi.org/10.1090/mcom/3943.
Chicago author-date (all authors)
Goedgebeur, Jan, Jorik Jooken, On-Hei Solomon Lo, Ben Seamone, and Carol Zamfirescu. 2024. “Few Hamiltonian Cycles in Graphs with One or Two Vertex Degrees.” MATHEMATICS OF COMPUTATION 93 (350): 3059–3082. doi:10.1090/mcom/3943.
Vancouver
1.
Goedgebeur J, Jooken J, Lo O-HS, Seamone B, Zamfirescu C. Few hamiltonian cycles in graphs with one or two vertex degrees. MATHEMATICS OF COMPUTATION. 2024;93(350):3059–82.
IEEE
[1]
J. Goedgebeur, J. Jooken, O.-H. S. Lo, B. Seamone, and C. Zamfirescu, “Few hamiltonian cycles in graphs with one or two vertex degrees,” MATHEMATICS OF COMPUTATION, vol. 93, no. 350, pp. 3059–3082, 2024.
@article{01J30GZBXP5CVXAG367GNBW05T,
  abstract     = {{Inspired by Sheehan's conjecture that no 4 -regular graph contains exactly one hamiltonian cycle, we prove results on hamiltonian cycles in regular graphs and nearly regular graphs. We fully disprove a conjecture of Haythorpe on the minimum number of hamiltonian cycles in regular hamiltonian graphs, thereby extending a result of Zamfirescu, as well as correct and complement Haythorpe's computational enumerative results from [Exp. Math. 27 (2018), no. 4, 426-430]. Thereafter, we use the Lov<acute accent>asz Local Lemma to extend Thomassen's independent dominating set method. This extension allows us to find a second hamiltonian cycle that inherits linearly many edges from the first hamiltonian cycle. Regarding the limitations of this method, we answer a question of Haxell, Seamone, and Verstraete, and settle the first open case of a problem of Thomassen by showing that for k is an element of {5, 6} there exist infinitely many k -regular hamiltonian graphs having no independent dominating set with respect to a prescribed hamiltonian cycle. Motivated by an observation of Aldred and Thomassen, we prove that for every kappa is an element of {2, 3} and any positive integer k, there are infinitely many non -regular graphs of connectivity kappa containing exactly one hamiltonian cycle and in which every vertex has degree 3 or 2k.}},
  author       = {{Goedgebeur, Jan and  Jooken, Jorik and  Lo, On-Hei Solomon and  Seamone, Ben and Zamfirescu, Carol}},
  issn         = {{0025-5718}},
  journal      = {{MATHEMATICS OF COMPUTATION}},
  keywords     = {{INDEPENDENT DOMINATING SETS,REGULAR GRAPHS,Hamiltonian cycle,regular graph,Lovasz Local Lemma}},
  language     = {{eng}},
  number       = {{350}},
  pages        = {{3059--3082}},
  title        = {{Few hamiltonian cycles in graphs with one or two vertex degrees}},
  url          = {{http://doi.org/10.1090/mcom/3943}},
  volume       = {{93}},
  year         = {{2024}},
}
Altmetric
View in Altmetric
Web of Science
Times cited: