Abstract
We study 2k-factors in (2 r+ 1) -regular graphs. Hanson, Loten, and Toft proved that every (2 r+ 1) -regular graph with at most 2r cut-edges has a 2-factor. We generalize their result by proving for k≤ (2 r+ 1) / 3 that every (2 r+ 1) -regular graph with at most 2 r- 3 (k- 1) cut-edges has a 2k-factor. Both the restriction on k and the restriction on the number of cut-edges are sharp. We characterize the graphs that have exactly 2 r- 3 (k- 1) + 1 cut-edges but no 2k-factor. For k> (2 r+ 1) / 3 , there are graphs without cut-edges that have no 2k-factor, as studied by Bollobás, Saito, and Wormald.
Original language | English (US) |
---|---|
Pages (from-to) | 199-207 |
Number of pages | 9 |
Journal | Graphs and Combinatorics |
Volume | 37 |
Issue number | 1 |
DOIs | |
State | Published - Jan 2021 |
Keywords
- Cut-edge
- Graph factor
- Matching
- Regular graph
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics