×

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.)
PDF BibTeX XML Cite
Full Text: EuDML