On Hamiltonian cycles in 4- and 5-connected plane triangulations

摘要

We prove that for every 5-connected plane triangulation T, and for every set A of facial cycles of T there is a Hamiltonian Cycle in T that contains two edges of each cycle in A, provided any two distinct cycles in A have distance at least three in T. (It remains open, whether a similar statement holds true if distance at least three is replaced with distance at least two or one.) Furthermore, it is shown that there is no such theorem for non-5-connected plane triangulations.