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
topHow 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) MR1055084
- Garey M.R., Johnson D.S., Tarjan R.E., The plane Hamiltonian problem is NP-complete, SIAM J. Comput. 5 (1968), 704-714. (1968) MR0444516
- Grünbaum B., Convex Polytopes, Interscience New York (1967). (1967) MR0226496
- 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 ?
topYou 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.