Geodesic
Simple algorithm for finding a second Hamilton cycle
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 9 (2012), pp. 151-155.

Voir la notice de l'article provenant de la source Math-Net.Ru

A classical theorem of C. A. B. Smith states that for every edge $e$ of a cubic graph $G$, the number of Hamilton cycles containing $e$ in $G$ is an even number. Tutte proved Smith's theorem using a nonconstructive parity argument. Thomason later invented the lollipop algorithm and provided a first constructive proof. We describe a simple algorithm based on Tutte's proof, thus providing an alternative constructive proof of Smith's theorem. Also this algorithm is exponential in the worst case.
Keywords: Smith Theorem, cubic graph, Hamilton cycle, lollipop algorithm, parity argument. 
@article{SEMR_2012_9_a18,
     author = {Tommy Jensen},
     title = {Simple algorithm for finding a second {Hamilton} cycle},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {151--155},
     publisher = {mathdoc},
     volume = {9},
     year = {2012},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2012_9_a18/}
}
TY  - JOUR
AU  - Tommy Jensen
TI  - Simple algorithm for finding a second Hamilton cycle
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2012
SP  - 151
EP  - 155
VL  - 9
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2012_9_a18/
LA  - en
ID  - SEMR_2012_9_a18
ER  - 
%0 Journal Article
%A Tommy Jensen
%T Simple algorithm for finding a second Hamilton cycle
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2012
%P 151-155
%V 9
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2012_9_a18/
%G en
%F SEMR_2012_9_a18
Tommy Jensen. Simple algorithm for finding a second Hamilton cycle. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 9 (2012), pp. 151-155. http://geodesic.mathdoc.fr/item/SEMR_2012_9_a18/

[1] J.A. Bondy, “Basic Graph Theory: Paths and Cycles”, Handbook of Combinatorics, eds. Graham, R., Grötschel, M., Lovász, L., Elsevier Science B.V., 1995 | MR | Zbl

[2] K. Cameron, “Krawczyk's graphs show Thomason's algorithm for finding a second Hamilton cycle through a given edge in a cubic graph is exponential”, Fifth Czech-Slovak Symposium on Combinatorics, Graph Theory, Algorithms and Applications, Prague, SIAM Conference on Discrete Mathematics, Toronto; July 1998

[3] M. Chrobak, S. Poljak, “On common edges in optimal solutions to traveling salesman and other optimization problems”, Discrete Appl. Math., 20 (1988), 101–111 | DOI | MR | Zbl

[4] A. Krawczyk, “The Complexity of Finding a Second Hamiltonian Cycle in Cubic Graphs”, J. Comput. Syst. Sci., 58:3 (1999), 641–647 | DOI | MR | Zbl

[5] C.H. Papadimitriou, “On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence”, J. Comput. Syst. Sci., 48:3 (1994), 498–532 | DOI | MR | Zbl

[6] A.G. Thomason, “Hamilton cycles and uniquely edge-colourable graphs”, Ann. of Discrete Math., 3 (1978), 259–268 | DOI | MR | Zbl

[7] W.T. Tutte, “On Hamilton circuits”, J. London Math. Soc., 21 (1946), 98–101 | DOI | MR | Zbl