Simple algorithm for finding a second Hamilton cycle

zbMATH Open1330.05094MaRDI QIDQ890906FDOQ890906

Authors: T. R. Jensen 

Publication date: 16 November 2015

Published in: Sibirskie Elektronnye Matematicheskie Izvestiya (Search for Journal in Brave)

Full work available at URL: http://semr.math.nsc.ru/v9/p151-155.pdf

Recommendations

• The complexity of finding a second Hamiltonian cycle in cubic graphs
• The complexity of Thomason's algorithm for finding a second Hamiltonian cycle
• Thomason's algorithm for finding a second Hamiltonian circuit through a given edge in a cubic graph is exponential on Krawczyk's graphs
• A Hamiltonian cycle in the square of a 2-connected graph in linear time
• On the Approximation of Finding A(nother) Hamiltonian Cycle in Cubic Hamiltonian Graphs

zbMATH Keywords

cubic graphHamilton cyclelollipop algorithmparity argumentSmith theorem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45)

Cited In (3)

• A parity theorem about trees with specified degrees
• Title not available (Why is that?)
• 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: Simple algorithm for finding a second Hamilton cycle

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q890906)