## Abstract

Let k ≥ 3 be an integer, h_{k}(G) be the number of vertices of degree at least 2k in a graph G, and ℓ_{k}(G) be the number of vertices of degree at most 2k - 2 in G. Dirac and Erdos proved in 1963 that if h_{k}(G) - ℓ_{k}(G) ≥ k^{2} + 2k - 4, then G contains k vertex-disjoint cycles. For each k ≥ 2, they also showed an infinite sequence of graphs G_{k}(n) with h_{k}(G_{k}(n)) - ℓk(G_{k}(n)) = 2k - 1 such that G_{k}(n) does not have k disjoint cycles. Recently, the authors proved that, for k ≥ 2, a bound of 3k is sufficient to guarantee the existence of k disjoint cycles, and presented for every k a graph G_{0}(k) with h_{k}(G_{0}(k)) - ℓk(G_{0}(k)) = 3k - 1 and no k disjoint cycles. The goal of this paper is to refine and sharpen this result. We show that the Dirac-Erdos construction is optimal in the sense that for every k ≥ 2, there are only finitely many graphs G with h_{k}(G) - ℓ_{k}(G) ≥ 2k but no k disjoint cycles. In particular, every graph G with |V(G)| ≥ 19k and h_{k}(G) - ℓ_{k}(G) ≥ 2k contains k disjoint cycles.

Original language | English (US) |
---|---|

Pages (from-to) | 387-397 |

Number of pages | 11 |

Journal | Combinatorics Probability and Computing |

Volume | 27 |

Issue number | 3 |

DOIs | |

State | Published - May 1 2018 |

## ASJC Scopus subject areas

- Theoretical Computer Science
- Statistics and Probability
- Computational Theory and Mathematics
- Applied Mathematics