Title of article :
Hamilton cycles in maximal planar graphs
Author/Authors :
Helde، نويسنده , , Guido and Vieten، نويسنده , , Oliver، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2006
Abstract :
A classical result of Whitney states that each maximal planar graph without separating triangles is hamiltonian, where a separating triangle is a triangle whose removal separates the graph. We extend Whitneyʹs Theorem by allowing some separating triangles. More precisely we define a tree B whose vertices are the separating triangles of the given maximal planar graph G and we show that if each vertex of the tree B has at most 2 children, then G is hamiltonian for any two boundary edges. Furthermore, it is shown that the conclusion of Whitneyʹs Theorem still holds if there are exactly three separating triangles.
Keywords :
maximal planar graph , separating triangle , Hamilton cycle
Journal title :
Electronic Notes in Discrete Mathematics
Journal title :
Electronic Notes in Discrete Mathematics