# zbMATH — the first resource for mathematics

Note on Petri and Hamiltonian cycles in cubic polyhedral graphs. (English) Zbl 0807.05044
A Petri cycle in a cubic graph is one, any two (but not three) consecutive edges of which (including the first and last) lie on a common face. Its existence can be recognized in $$O(n)$$ time, where $$n$$ is the number of vertices of the graph. Deciding the existence of a Hamilton cycle in a cubic polyhedral (planar and 3-connected) graph is known to be NP-complete.
Here the authors define an operation of ‘cutting off’ a vertex in a cubic plane graph $$G$$ resulting in another cubic plane graph. Extending this to a set $$S$$ of vertices one gets a cubic plane graph $$G\nabla S$$. They prove that a cubic plane graph $$G$$ is Hamiltonian if and only if there exists a set $$S$$ of vertices of $$G$$ such that $$G\nabla S$$ has a Petri Hamiltonian cycle. They further show that if $$G$$ is a cubic polyhedral $$n$$-vertex graph with a Petri Hamilton cycle then the faces of $$G$$ are multi-three-gonal (i.e. face size $$\equiv 0\pmod 3$$) and $$4\leq n\equiv 0\pmod 4$$, $$n\neq 8$$.
##### MSC:
 05C38 Paths and cycles 05C45 Eulerian and Hamiltonian graphs 52B05 Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.)
Full Text: