| 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:
|
http://hdl.handle.net/10338.dmlcz/118681 |
| . |
| 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 |
| . |
