$K_2$-Hamiltonian Graphs: II
| Autor: | Goedgebeur, Jan, Renders, Jarne, Wiener, Gábor, Zamfirescu, Carol T. |
|---|---|
| Rok vydání: | 2023 |
| Předmět: | |
| Zdroj: | J. Graph Theory. 2024; 105: 580-611 |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1002/jgt.23057 |
| Popis: | In this paper we use theoretical and computational tools to continue our investigation of $K_2$-hamiltonian graphs, that is, graphs in which the removal of any pair of adjacent vertices yields a hamiltonian graph, and their interplay with $K_1$-hamiltonian graphs, that is, graphs in which every vertex-deleted subgraph is hamiltonian. Perhaps surprisingly, there exist graphs that are both $K_1$- and $K_2$-hamiltonian, yet non-hamiltonian, for example, the Petersen graph. Gr\"unbaum conjectured that every planar $K_1$-hamiltonian graph must itself be hamiltonian; Thomassen disproved this conjecture. Here we show that even planar graphs that are both $K_1$- and $K_2$-hamiltonian need not be hamiltonian, and that the number of such graphs grows at least exponentially. Motivated by results of Aldred, McKay, and Wormald, we determine for every integer $n$ that is not 14 or 17 whether there exists a $K_2$-hypohamiltonian, that is, non-hamiltonian and $K_2$-hamiltonian, graph of order $n$, and characterise all orders for which such cubic graphs and such snarks exist. We also describe the smallest cubic planar graph which is $K_2$-hypohamiltonian, as well as the smallest planar $K_2$-hypohamiltonian graph of girth $5$. We conclude with open problems and by correcting two inaccuracies from the first article. Comment: 30 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|