Article
Full entry |
PDF
(0.1 MB)
Feedback
PDF
(0.1 MB)
Feedback
Keywords:
Hamiltonian cycles; Petrie cycles; cubic polyhedral graphs
Hamiltonian cycles; Petrie cycles; cubic polyhedral graphs
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.
References:
[1] Coxeter H.S.M.: Regular Polytopes. MacMillan London (1948). MR 0151873 | Zbl 0031.06502
[2] Fleischner H.: Eulerian graphs and related topics, Part 1, Vol. 1. North-Holland Amsterdam (1990). MR 1055084
[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
[4] Grünbaum B.: Convex Polytopes. Interscience New York (1967). MR 0226496
[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. MR 0969251 | Zbl 0607.05051
[6] Malkevitch J.: Polytopal graphs. Selected topics in graph theory III L.W. Beineke and R.J. Wilson Academic Press London (1988), 169-188. MR 1205401 | Zbl 0678.05015
Search
Partner of
