The complexity of finding a second Hamiltonian cycle in cubic graphs

DOI10.1006/jcss.1998.1611zbMath0939.68093OpenAlexW2066230947MaRDI QIDQ1307702

Adam Krawczyk

Publication date: 9 November 1999

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.1998.1611

zbMATH Keywords

Hamiltonian cyclescubic graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (7)

THE COMPLEXITY OF THOMASON’S ALGORITHM FOR FINDING A SECOND HAMILTONIAN CYCLE ⋮ Understanding PPA-completeness ⋮ Long cycles in Hamiltonian graphs ⋮ A parity theorem about trees with specified degrees ⋮ A short note on graphs with long Thomason chains ⋮ Unnamed Item ⋮ A PPA parity theorem about trees in a bipartite graph

Cites Work

• On existence theorems
• On the complexity of the parity argument and other inefficient proofs of existence
• Hamiltonian Cycles and Uniquely Edge Colourable Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The complexity of finding a second Hamiltonian cycle in cubic graphs