Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8903162 | Discrete Mathematics | 2018 | 10 Pages |
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 tâ¥1, 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 kâ¥2, 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 kâ¥2.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Ronald J. Gould, Kazuhide Hirohata, Ariel Keller,