Geodesic
Note on Petrie and Hamiltonian cycles in cubic polyhedral graphs
Commentationes Mathematicae Universitatis Carolinae, Tome 35 (1994) no. 2, pp. 413-417

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

In this note we show that deciding the existence of a Hamiltonian cycle in a cubic plane graph is equivalent to the problem of the existence of an associated cubic plane multi-3-gonal graph with a Hamiltonian cycle which takes alternately left and right edges at each successive vertex, i.e\. it is also a Petrie cycle. The Petrie Hamiltonian cycle in an $n$-vertex plane cubic graph can be recognized by an $O(n)$-algorithm.
Classification : 05C38, 05C45, 52B05
Keywords: Hamiltonian cycles; Petrie cycles; cubic polyhedral graphs 
@article{CMUC_1994__35_2_a22,
     author = {Ivan\v{c}o, J. and Jendro\v{l}, S. and Tk\'a\v{c}, M.},
     title = {Note on {Petrie} and {Hamiltonian} cycles in cubic polyhedral graphs},
     journal = {Commentationes Mathematicae Universitatis Carolinae},
     pages = {413--417},
     publisher = {mathdoc},
     volume = {35},
     number = {2},
     year = {1994},
     mrnumber = {1286589},
     zbl = {0807.05044},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMUC_1994__35_2_a22/}
}
TY  - JOUR
AU  - Ivančo, J.
AU  - Jendroľ, S.
AU  - Tkáč, M.
TI  - Note on Petrie and Hamiltonian cycles in cubic polyhedral graphs
JO  - Commentationes Mathematicae Universitatis Carolinae
PY  - 1994
SP  - 413
EP  - 417
VL  - 35
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/CMUC_1994__35_2_a22/
LA  - en
ID  - CMUC_1994__35_2_a22
ER  - 
%0 Journal Article
%A Ivančo, J.
%A Jendroľ, S.
%A Tkáč, M.
%T Note on Petrie and Hamiltonian cycles in cubic polyhedral graphs
%J Commentationes Mathematicae Universitatis Carolinae
%D 1994
%P 413-417
%V 35
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/CMUC_1994__35_2_a22/
%G en
%F CMUC_1994__35_2_a22
Ivančo, J.; Jendroľ, S.; Tkáč, M. Note on Petrie and Hamiltonian cycles in cubic polyhedral graphs. Commentationes Mathematicae Universitatis Carolinae, Tome 35 (1994) no. 2, pp. 413-417. http://geodesic.mathdoc.fr/item/CMUC_1994__35_2_a22/