Generation and new infinite families of K2-hypohamiltonian graphs
- Author
- Jan Goedgebeur (UGent) , Jarne Renders and Carol Zamfirescu (UGent)
- 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
- |
- |
- 314.99 KB
-
(...).pdf
- full text (Published version)
- |
- UGent only
- |
- |
- 471.91 KB
Citation
Please use this url to cite or link to this publication: http://hdl.handle.net/1854/LU-01J30C2MM02JZ2HCMN11NV1PEG
- 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: