Advanced search
2 files | 786.89 KB Add to list

Generation and new infinite families of K2-hypohamiltonian graphs

Author
Organization
Project
Abstract
We present an algorithm which can generate all pairwise non-isomorphic K2-hypohamiltonian graphs, i.e. non-hamiltonian graphs in which the removal of any pair of adjacent vertices yields a hamiltonian graph, of a given order. We introduce new bounding criteria specifically designed for K2-hypohamiltonian graphs, allowing us to improve upon earlier computational results. Specifically, we characterise the orders for which K2-hypohamiltonian graphs exist and improve existing lower bounds on the orders of the smallest planar and the smallest bipartite K2-hypohamiltonian graphs. Furthermore, we describe a new operation for creating K2-hypohamiltonian graphs that preserves planarity under certain conditions and use it to prove the existence of a planar K2-hypohamiltonian graph of order n for every integer n >= 134. Additionally, motivated by a theorem of Thomassen on hypohamiltonian graphs, we show the existence K2-hypohamiltonian graphs with large maximum degree and size.
Keywords
Hamiltonian cycle, Hypohamiltonian, Exhaustive generation, Planar, Infinite family, Maximum degree

Downloads

  • 2311.10593v2.pdf
    • full text (Accepted manuscript)
    • |
    • open access
    • |
    • PDF
    • |
    • 314.99 KB
  • (...).pdf
    • full text (Published version)
    • |
    • UGent only
    • |
    • PDF
    • |
    • 471.91 KB

Citation

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

MLA
Goedgebeur, Jan, et al. “Generation and New Infinite Families of K2-Hypohamiltonian Graphs.” DISCRETE MATHEMATICS, vol. 347, no. 7, 2024, doi:10.1016/j.disc.2024.113981.
APA
Goedgebeur, J., Renders, J., & Zamfirescu, C. (2024). Generation and new infinite families of K2-hypohamiltonian graphs. DISCRETE MATHEMATICS, 347(7). https://doi.org/10.1016/j.disc.2024.113981
Chicago author-date
Goedgebeur, Jan, Jarne Renders, and Carol Zamfirescu. 2024. “Generation and New Infinite Families of K2-Hypohamiltonian Graphs.” DISCRETE MATHEMATICS 347 (7). https://doi.org/10.1016/j.disc.2024.113981.
Chicago author-date (all authors)
Goedgebeur, Jan, Jarne Renders, and Carol Zamfirescu. 2024. “Generation and New Infinite Families of K2-Hypohamiltonian Graphs.” DISCRETE MATHEMATICS 347 (7). doi:10.1016/j.disc.2024.113981.
Vancouver
1.
Goedgebeur J, Renders J, Zamfirescu C. Generation and new infinite families of K2-hypohamiltonian graphs. DISCRETE MATHEMATICS. 2024;347(7).
IEEE
[1]
J. Goedgebeur, J. Renders, and C. Zamfirescu, “Generation and new infinite families of K2-hypohamiltonian graphs,” DISCRETE MATHEMATICS, vol. 347, no. 7, 2024.
@article{01J30C2MM02JZ2HCMN11NV1PEG,
  abstract     = {{We present an algorithm which can generate all pairwise non-isomorphic K2-hypohamiltonian graphs, i.e. non-hamiltonian graphs in which the removal of any pair of adjacent vertices yields a hamiltonian graph, of a given order. We introduce new bounding criteria specifically designed for K2-hypohamiltonian graphs, allowing us to improve upon earlier computational results. Specifically, we characterise the orders for which K2-hypohamiltonian graphs exist and improve existing lower bounds on the orders of the smallest planar and the smallest bipartite K2-hypohamiltonian graphs. Furthermore, we describe a new operation for creating K2-hypohamiltonian graphs that preserves planarity under certain conditions and use it to prove the existence of a planar K2-hypohamiltonian graph of order n for every integer n >= 134. Additionally, motivated by a theorem of Thomassen on hypohamiltonian graphs, we show the existence K2-hypohamiltonian graphs with large maximum degree and size.}},
  articleno    = {{113981}},
  author       = {{Goedgebeur, Jan and  Renders, Jarne and Zamfirescu, Carol}},
  issn         = {{0012-365X}},
  journal      = {{DISCRETE MATHEMATICS}},
  keywords     = {{Hamiltonian cycle,Hypohamiltonian,Exhaustive generation,Planar,Infinite family,Maximum degree}},
  language     = {{eng}},
  number       = {{7}},
  pages        = {{15}},
  title        = {{Generation and new infinite families of K2-hypohamiltonian graphs}},
  url          = {{http://doi.org/10.1016/j.disc.2024.113981}},
  volume       = {{347}},
  year         = {{2024}},
}

Altmetric
View in Altmetric
Web of Science
Times cited: