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 vertex-disjoint cycles in a graph . For an integer , let be the smallest sum of degrees of independent vertices of . We prove that if has order at least and , with , then contains vertex-disjoint cycles. We also show that the degree sum condition on is sharp and conjecture a degree sum condition on sufficient to imply contains vertex-disjoint cycles for . |
| |
Keywords: | Vertex-disjoint cycles Minimum degree sum Degree sequence |
本文献已被 ScienceDirect 等数据库收录! |
|