Minimum degree conditions for vertex-disjoint even cycles in large graphs

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 ck s...

Full description

Saved in:
Bibliographic Details
Published in:Advances in applied mathematics 2014-03, Vol.54, p.105-120
Main Authors: Chiba, Shuya, Fujita, Shinya, Kawarabayashi, Ken-ichi, Sakuma, Tadashi
Format: Article
Language:English
Subjects:
Blocking
Even cycle
Graphs
Integers
Mathematical analysis
Minimum degree
Theorems
Theta graph
Vertex-disjoint cycles
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 ck such that if G is a graph with at least ck 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 (p⩾k⩾2), or (iii) k=1 and each block of G is either a K2 or an odd cycle.
ISSN:0196-8858
1090-2074
DOI:10.1016/j.aam.2013.12.001