Hamiltonian paths in odd graphs
| Autor: | Luerbio Faria, Figueiredo Celina M.H. De, Letícia Rodrigues Bueno, Fonseca Guilherme D. Da |
|---|---|
| Rok vydání: | 2009 |
| Předmět: | |
| Zdroj: | Applicable Analysis and Discrete Mathematics. 3:386-394 |
| ISSN: | 2406-100X 1452-8630 |
| DOI: | 10.2298/aadm0902386b |
| Popis: | Lov?sz conjectured that every connected vertex-transitive graph has a Hamiltonian path. The odd graphs Ok form a well-studied family of connected, k-regular, vertex-transitive graphs. It was previously known that Ok has Hamiltonian paths for k ? 14. A direct computation of Hamiltonian paths in Ok is not feasible for large values of k, because Ok has (2k - 1, k - 1) vertices and k/2 (2k - 1, k - 1) edges. We show that Ok has Hamiltonian paths for 15 ? k ? 18. Instead of directly running any heuristics, we use existing results on the middle levels problem, therefore further relating these two fundamental problems, namely finding a Hamiltonian path in the odd graph and finding a Hamiltonian cycle in the corresponding middle levels graph. We show that further improved results for the middle levels problem can be used to find Hamiltonian paths in Ok for larger values of k. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|