Simple algorithm for finding a second Hamilton cycle

MaRDI QIDQ890906zbMATH OpenFDO

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

zbMATH Keywords

cubic graphHamilton cyclelollipop algorithmparity argumentSmith theorem

Mathematics Subject Classification ID

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

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

Cited in

(4)

• A parity theorem about trees with specified degrees
• Thomason's algorithm for finding a second Hamiltonian circuit through a given edge in a cubic graph is exponential on Krawczyk's graphs
• scientific article; zbMATH DE number 7559398 (Why is no real title available?)
• The complexity of Thomason's algorithm for finding a second Hamiltonian cycle

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)