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/