Article ID Journal Published Year Pages File Type
4624753 Advances in Applied Mathematics 2014 16 Pages PDF
Abstract

We prove a variant of a theorem of Corrádi and Hajnal (1963) [4] which says that if a graph G has at least 3k vertices and its minimum degree is at least 2k, then G contains k vertex-disjoint cycles. Specifically, our main result is the following. For any positive integer k  , there is a constant ckck such that if G   is a graph with at least ckck vertices and the minimum degree of G is at least 2k, then (i) G contains k   vertex-disjoint even cycles, or (ii) (2k−1)K1∨pK2⊂G⊂K2k−1∨pK2(2k−1)K1∨pK2⊂G⊂K2k−1∨pK2 (p⩾k⩾2p⩾k⩾2), or (iii) k=1k=1 and each block of G   is either a K2K2 or an odd cycle.

Related Topics
Physical Sciences and Engineering Mathematics Applied Mathematics
Authors
, , , ,