Title of article :
Hamiltonian cycles through prescribed edges of 4-connected maximal planar graphs
Author/Authors :
M. and Gِring، نويسنده , , F. and Harant، نويسنده , , J.، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2010
Pages :
4
From page :
1491
To page :
1494
Abstract :
In 1956, W.T. Tutte proved that every 4-connected planar graph is hamiltonian. Moreover, in 1997, D.P. Sanders extended this to the result that a 4-connected planar graph contains a hamiltonian cycle through any two of its edges. It is shown that Sanders’ result is best possible by constructing 4-connected maximal planar graphs with three edges a large distance apart such that any hamiltonian cycle misses one of them. If the maximal planar graph is 5-connected then such a construction is impossible.
Keywords :
maximal planar graph , Prescribed edges , hamiltonian cycle
Journal title :
Discrete Mathematics
Serial Year :
2010
Journal title :
Discrete Mathematics
Record number :
1599368
Link To Document :
بازگشت