Cut-edges and regular factors in regular graphs of odd degree

We study \(2k\)-factors in \((2r+1)\)-regular graphs. Hanson, Loten, and Toft proved that every \((2r+1)\)-regular graph with at most \(2r\) cut-edges has a \(2\)-factor. We generalize their result by proving for \(k\le(2r+1)/3\) that every \((2r+1)\)-regular graph with at most \(2r-3(k-1)\) cut-edg...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2018-06
Main Authors: Kostochka, Alexander V, Raspaud, André, Toft, Bjarne, West, Douglas B, Zirlin, Dara
Format: Article
Language:English
Subjects:
Graph theory
Graphs
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We study \(2k\)-factors in \((2r+1)\)-regular graphs. Hanson, Loten, and Toft proved that every \((2r+1)\)-regular graph with at most \(2r\) cut-edges has a \(2\)-factor. We generalize their result by proving for \(k\le(2r+1)/3\) that every \((2r+1)\)-regular graph with at most \(2r-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 \(2r-3(k-1)+1\) cut-edges but no \(2k\)-factor. For \(k>(2r+1)/3\), there are graphs without cut-edges that have no \(2k\)-factor, as studied by Bollobás, Saito, and Wormald.
ISSN:2331-8422