Thomason's algorithm for finding a second Hamiltonian circuit through a given edge in a cubic graph is exponential on Krawczyk's graphs (Q5937919)

Smith [see \textit{W. T. Tutte}, J. Lond. Math. Soc. 21, 98-101 (1946; Zbl 0061.41306)] proved that in a cubic graph every edge is contained in an even number of Hamiltonian cycles. Consequently, if a cubic graph has a Hamiltonian cycle through an edge \(e\), then there is a second Hamiltonian cycle through \(e\). In 1978, Thomason presented an algorithm to find a second Hamiltonian cycle, which is finite and completely deterministic for cubic graphs; see \textit{A. G. Thomason} [Ann. Discrete Math. 3, 259-268 (1978; Zbl 0382.05039)]. Recently, Krawczyk found a family of graphs on which Thomason's algorithm is exponential. The author gives a proof that Thomason's algorithm is exponential for a family of cubic planar graphs, which is a variant of Krawczyk's family.