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


A generalization of Tutte’s theorem on Hamiltonian cycles in planar graphs
Authors:Jochen Harant  Stefan Senitsch
Institution:Department of Mathematics, Technical University of Ilmenau, D-98684 Ilmenau, Germany
Abstract:In 1956, W.T. Tutte proved that a 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. We prove that a planar graph G has a cycle containing a given subset X of its vertex set and any two prescribed edges of the subgraph of G induced by X if |X|≥3 and if X is 4-connected in G. If X=V(G) then Sanders’ result follows.
Keywords:Planar graph  Hamiltonian cycle
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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