Abstract
In 1963, Corradi and Hajnal proved that for all k≥1 and n≥3k, every (simple) graph G on n vertices with minimum degree δ(G)≥2k contains k disjoint cycles. The same year, Dirac described the 3-connected multigraphs not containing two disjoint cycles and asked the more general question: Which (2k—1)-connected multigraphs do not contain k disjoint cycles? Recently, the authors characterized the simple graphs G with minimum degree δ(G)≥2k—1 that do not contain k disjoint cycles. We use this result to answer Dirac's question in full.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 77-86 |
| Number of pages | 10 |
| Journal | Combinatorica |
| Volume | 37 |
| Issue number | 1 |
| DOIs | |
| State | Published - Feb 1 2017 |
Keywords
- 05C15
- 05C35
- 05C40
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Computational Mathematics
Fingerprint
Dive into the research topics of 'The (2k-1)-connected multigraphs with at most k-1 disjoint cycles'. Together they form a unique fingerprint.Cite this
- APA
- Standard
- Harvard
- Vancouver
- Author
- BIBTEX
- RIS