Cut-Edges and Regular Factors in Regular Graphs of Odd Degree

We study 2 k -factors in ( 2 r + 1 ) -regular graphs. Hanson, Loten, and Toft proved that every ( 2 r + 1 ) -regular graph with at most 2 r 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...

Full description

Saved in:
Bibliographic Details
Published in:Graphs and combinatorics 2021, Vol.37 (1), p.199-207
Main Authors: Kostochka, Alexandr V., Raspaud, André, Toft, Bjarne, West, Douglas B., Zirlin, Dara
Format: Article
Language:English
Subjects:
Combinatorics
Engineering Design
Graph theory
Graphs
Mathematics
Mathematics and Statistics
Original Paper
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We study 2 k -factors in ( 2 r + 1 ) -regular graphs. Hanson, Loten, and Toft proved that every ( 2 r + 1 ) -regular graph with at most 2 r 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 2 k -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 2 k -factor. For k > ( 2 r + 1 ) / 3 , there are graphs without cut-edges that have no 2 k -factor, as studied by Bollobás, Saito, and Wormald.
ISSN:0911-0119
1435-5914
DOI:10.1007/s00373-020-02242-0