首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Hamiltonian cycles through prescribed edges of 4-connected maximal planar graphs
Authors:F Göring
Institution:a Department of Mathematics, Technical University of Chemnitz, Germany
b Institute of Mathematics, Technical University of Ilmenau, Germany
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  Hamiltonian cycle  Prescribed edges
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号