Generation and New Infinite Families of $K_2$-hypohamiltonian Graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916141249593344 |
|---|---|
| author | Goedgebeur, Jan Renders, Jarne Zamfirescu, Carol T. |
| author_facet | Goedgebeur, Jan Renders, Jarne Zamfirescu, Carol T. |
| contents | We present an algorithm which can generate all pairwise non-isomorphic $K_2$-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 $K_2$-hypohamiltonian graphs, allowing us to improve upon earlier computational results. Specifically, we characterise the orders for which $K_2$-hypohamiltonian graphs exist and improve existing lower bounds on the orders of the smallest planar and the smallest bipartite $K_2$-hypohamiltonian graphs. Furthermore, we describe a new operation for creating $K_2$-hypohamiltonian graphs that preserves planarity under certain conditions and use it to prove the existence of a planar $K_2$-hypohamiltonian graph of order $n$ for every integer $n\geq 134$. Additionally, motivated by a theorem of Thomassen on hypohamiltonian graphs, we show the existence $K_2$-hypohamiltonian graphs with large maximum degree and size. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_10593 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Generation and New Infinite Families of $K_2$-hypohamiltonian Graphs Goedgebeur, Jan Renders, Jarne Zamfirescu, Carol T. Combinatorics Discrete Mathematics 05C38, 05C45, 05C85, 05C30, 05C76, 05C10 We present an algorithm which can generate all pairwise non-isomorphic $K_2$-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 $K_2$-hypohamiltonian graphs, allowing us to improve upon earlier computational results. Specifically, we characterise the orders for which $K_2$-hypohamiltonian graphs exist and improve existing lower bounds on the orders of the smallest planar and the smallest bipartite $K_2$-hypohamiltonian graphs. Furthermore, we describe a new operation for creating $K_2$-hypohamiltonian graphs that preserves planarity under certain conditions and use it to prove the existence of a planar $K_2$-hypohamiltonian graph of order $n$ for every integer $n\geq 134$. Additionally, motivated by a theorem of Thomassen on hypohamiltonian graphs, we show the existence $K_2$-hypohamiltonian graphs with large maximum degree and size. |
| title | Generation and New Infinite Families of $K_2$-hypohamiltonian Graphs |
| topic | Combinatorics Discrete Mathematics 05C38, 05C45, 05C85, 05C30, 05C76, 05C10 |
| url | https://arxiv.org/abs/2311.10593 |