J. Ivan\v co, S. Jendro\v l, M. Tk\' a\v c

J. Ivan\v co, S. Jendro\v l, M. Tk\' a\v c
Note on Petrie and Hamiltonian cycles in cubic polyhedral graphs

Comment.Math.Univ.Carolinae 35,2 (1994) 413-416.

Abstract: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.

Keywords: Hamiltonian cycles, Petrie cycles, cubic polyhedral graphs
AMS Subject Classification: 05C45, 05C38

PDF

J. Ivan\v co, S. Jendro\v l, M. Tk\' a\v c Note on Petrie and Hamiltonian cycles in cubic polyhedral graphs

J. Ivan\v co, S. Jendro\v l, M. Tk\' a\v c
Note on Petrie and Hamiltonian cycles in cubic polyhedral graphs