# Note on Petrie and Hamiltonian cycles in cubic polyhedral graphs

Jaroslav Ivančo; Stanislav Jendroľ; Michal Tkáč

Commentationes Mathematicae Universitatis Carolinae (1994)

- Volume: 35, Issue: 2, page 413-417
- ISSN: 0010-2628

## Access Full Article

top## Abstract

top## How to cite

topIvančo, Jaroslav, Jendroľ, Stanislav, and Tkáč, Michal. "Note on Petrie and Hamiltonian cycles in cubic polyhedral graphs." Commentationes Mathematicae Universitatis Carolinae 35.2 (1994): 413-417. <http://eudml.org/doc/22032>.

@article{Ivančo1994,

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.ei̇t is also a Petrie cycle. The Petrie Hamiltonian cycle in an $n$-vertex plane cubic graph can be recognized by an $O(n)$-algorithm.},

author = {Ivančo, Jaroslav, Jendroľ, Stanislav, Tkáč, Michal},

journal = {Commentationes Mathematicae Universitatis Carolinae},

keywords = {Hamiltonian cycles; Petrie cycles; cubic polyhedral graphs; algorithm; cubic polyhedral graph; Petri cycle; Hamilton cycle; NP-complete; cubic plane graph},

language = {eng},

number = {2},

pages = {413-417},

publisher = {Charles University in Prague, Faculty of Mathematics and Physics},

title = {Note on Petrie and Hamiltonian cycles in cubic polyhedral graphs},

url = {http://eudml.org/doc/22032},

volume = {35},

year = {1994},

}

TY - JOUR

AU - Ivančo, Jaroslav

AU - Jendroľ, Stanislav

AU - Tkáč, Michal

TI - Note on Petrie and Hamiltonian cycles in cubic polyhedral graphs

JO - Commentationes Mathematicae Universitatis Carolinae

PY - 1994

PB - Charles University in Prague, Faculty of Mathematics and Physics

VL - 35

IS - 2

SP - 413

EP - 417

AB - 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.ei̇t is also a Petrie cycle. The Petrie Hamiltonian cycle in an $n$-vertex plane cubic graph can be recognized by an $O(n)$-algorithm.

LA - eng

KW - Hamiltonian cycles; Petrie cycles; cubic polyhedral graphs; algorithm; cubic polyhedral graph; Petri cycle; Hamilton cycle; NP-complete; cubic plane graph

UR - http://eudml.org/doc/22032

ER -

## References

top- Coxeter H.S.M., Regular Polytopes, MacMillan London (1948). (1948) Zbl0031.06502MR0151873
- Fleischner H., Eulerian graphs and related topics, Part 1, Vol. 1, North-Holland Amsterdam (1990). (1990) Zbl0792.05091MR1055084
- Garey M.R., Johnson D.S., Tarjan R.E., The plane Hamiltonian problem is NP-complete, SIAM J. Comput. 5 (1968), 704-714. (1968) Zbl0346.05110MR0444516
- Grünbaum B., Convex Polytopes, Interscience New York (1967). (1967) Zbl0163.16603MR0226496
- 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. (1988) Zbl0607.05051MR0969251
- Malkevitch J., Polytopal graphs, Selected topics in graph theory III L.W. Beineke and R.J. Wilson Academic Press London (1988), 169-188. (1988) Zbl0678.05015MR1205401

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.