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

Abstract

top
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.

How to cite

top

Ivanč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
  1. Coxeter H.S.M., Regular Polytopes, MacMillan London (1948). (1948) Zbl0031.06502MR0151873
  2. Fleischner H., Eulerian graphs and related topics, Part 1, Vol. 1, North-Holland Amsterdam (1990). (1990) Zbl0792.05091MR1055084
  3. 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
  4. Grünbaum B., Convex Polytopes, Interscience New York (1967). (1967) Zbl0163.16603MR0226496
  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. (1988) Zbl0607.05051MR0969251
  6. 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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.