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


On the Burkard-Hammer condition for hamiltonian split graphs
Authors:Ngo Dac Tan
Institution:a Institute of Mathematics, 18 Hoang Quoc Viet Road, 10307 Hanoi, Viet Nam
b Provincial Office of Education and Training, Tuyen Quang, Viet Nam
Abstract:A graph G=(V,E) is called a split graph if there exists a partition V=IK such that the subgraphs of G induced by I and K are empty and complete graphs, respectively. In 1980, Burkard and Hammer gave a necessary but not sufficient condition for hamiltonian split graphs with |I|<|K|. In this paper, we show that the Burkard-Hammer condition is also sufficient for the existence of a Hamilton cycle in a split graph G such that 5≠|I|<|K| and the minimum degree δ(G)?|I|-3. For the case 5=|I|<|K|, all split graphs satisfying the Burkard-Hammer condition but having no Hamilton cycles are also described.
Keywords:primary 05C45  secondary 05C75
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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