Previous |  Up |  Next


Title: Note on Petrie and Hamiltonian cycles in cubic polyhedral graphs (English)
Author: Ivančo, J.
Author: Jendroľ, S.
Author: Tkáč, M.
Language: English
Journal: Commentationes Mathematicae Universitatis Carolinae
ISSN: 0010-2628 (print)
ISSN: 1213-7243 (online)
Volume: 35
Issue: 2
Year: 1994
Pages: 413-417
Category: math
Summary: 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. (English)
Keyword: Hamiltonian cycles
Keyword: Petrie cycles
Keyword: cubic polyhedral graphs
MSC: 05C38
MSC: 05C45
MSC: 52B05
idZBL: Zbl 0807.05044
idMR: MR1286589
Date available: 2009-01-08T18:12:07Z
Last updated: 2012-04-30
Stable URL:
Reference: [1] Coxeter H.S.M.: Regular Polytopes.MacMillan London (1948). Zbl 0031.06502, MR 0151873
Reference: [2] Fleischner H.: Eulerian graphs and related topics, Part 1, Vol. 1.North-Holland Amsterdam (1990). MR 1055084
Reference: [3] Garey M.R., Johnson D.S., Tarjan R.E.: The plane Hamiltonian problem is NP-complete.SIAM J. Comput. 5 (1968), 704-714. MR 0444516
Reference: [4] Grünbaum B.: Convex Polytopes.Interscience New York (1967). MR 0226496
Reference: [5] Holton D.A., McKay B.D.: The smallest non-hamiltonian 3-connected cubic planar graphs have 38 vertices.J. Comb. Theory B 45 (1988), 305-319. Zbl 0607.05051, MR 0969251
Reference: [6] Malkevitch J.: Polytopal graphs.Selected topics in graph theory III L.W. Beineke and R.J. Wilson Academic Press London (1988), 169-188. Zbl 0678.05015, MR 1205401


Files Size Format View
CommentatMathUnivCarolRetro_35-1994-2_23.pdf 176.4Kb application/pdf View/Open
Back to standard record
Partner of
EuDML logo