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


Hamiltonicity, independence number, and pancyclicity
Authors:Choongbum Lee Benny Sudakov
Institution:
  • Department of Mathematics, UCLA, Los Angeles, CA, 90095, United States
  • Abstract:A graph on n vertices is called pancyclic if it contains a cycle of length ? for all 3≤?n. In 1972, Erd?s proved that if G is a Hamiltonian graph on n>4k4 vertices with independence number k, then G is pancyclic. He then suggested that n=Ω(k2) should already be enough to guarantee pancyclicity. Improving on his and some other later results, we prove that there exists a constant c such that n>ck7/3 suffices.
    Keywords:
    本文献已被 ScienceDirect 等数据库收录!
    设为首页 | 免责声明 | 关于勤云 | 加入收藏

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