A short note on graphs with long Thomason chains

DOI10.1016/J.DISC.2021.112624zbMath1476.05039arXiv1903.02515OpenAlexW3201217816MaRDI QIDQ2237207

Adam Szady, Marcin Briański

Publication date: 27 October 2021

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1903.02515

zbMATH Keywords

cubic graphHamiltonian cycleSmith's theoremThomason's algorithm

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40) Eulerian and Hamiltonian graphs (05C45)

Cites Work

• Unnamed Item
• Unnamed Item
• The complexity of finding a second Hamiltonian cycle in cubic graphs
• Hamiltonian Cycles and Uniquely Edge Colourable Graphs
• THE COMPLEXITY OF THOMASON’S ALGORITHM FOR FINDING A SECOND HAMILTONIAN CYCLE
• Parameterized Algorithms
• Thomason's algorithm for finding a second Hamiltonian circuit through a given edge in a cubic graph is exponential on Krawczyk's graphs

This page was built for publication: A short note on graphs with long Thomason chains