The (2k-1)-connected multigraphs with at most k-1 disjoint cycles

In 1963, Corradi and Hajnal proved that for all k ≥1 and n ≥3 k , every (simple) graph G on n vertices with minimum degree δ( G )≥2 k 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 (...

Full description

Saved in:
Bibliographic Details
Published in:Combinatorica (Budapest. 1981) 2017-02, Vol.37 (1), p.77-86
Main Authors: Kierstead, Henry A., Kostochka, Alexandr V., Yeager, Elyse C.
Format: Article
Language:English
Subjects:
Banking industry
Combinatorics
Graph theory
Mathematics
Mathematics and Statistics
Original Paper
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:In 1963, Corradi and Hajnal proved that for all k ≥1 and n ≥3 k , every (simple) graph G on n vertices with minimum degree δ( G )≥2 k 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 (2 k —1)-connected multigraphs do not contain k disjoint cycles? Recently, the authors characterized the simple graphs G with minimum degree δ( G )≥2 k —1 that do not contain k disjoint cycles. We use this result to answer Dirac's question in full.
ISSN:0209-9683
1439-6912
DOI:10.1007/s00493-015-3291-8