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


On vertex-disjoint cycles and degree sum conditions
Authors:Ronald J Gould  Kazuhide Hirohata  Ariel Keller
Institution:1. Department of Mathematics and Computer Science, Emory University, Atlanta, GA 30322, USA;2. Department of Electronic and Computer Engineering, National Institute of Technology, Ibaraki College, Ibaraki, 312-8508, Japan
Abstract:This paper considers a degree sum condition sufficient to imply the existence of k vertex-disjoint cycles in a graph G. For an integer t1, let σt(G) be the smallest sum of degrees of t independent vertices of G. We prove that if G has order at least 7k+1 and σ4(G)8k?3, with k2, then G contains k vertex-disjoint cycles. We also show that the degree sum condition on σ4(G) is sharp and conjecture a degree sum condition on σt(G) sufficient to imply G contains k vertex-disjoint cycles for k2.
Keywords:Vertex-disjoint cycles  Minimum degree sum  Degree sequence
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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