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\).
05C38 Paths and cycles
05C45 Eulerian and Hamiltonian graphs
52B05 Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.)
Full Text: EuDML