A short note on graphs with long Thomason's chains

Abstract

We present a family of 3-connected cubic planar Hamiltonian graphs with an exponential number of steps required by Thomason's algorithm. The base of the exponent is approximately $\mathrm{1.1812...}$, which exceeds previous results in the area.

9 pages, 13 figures

Cited by in corpus (2)

• The Complexity of Iterated Reversible Computation
• Another Hamiltonian Cycle in Bipartite Pfaffian Graphs