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

Abstract: 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 l e (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'as, Saito, and Wormald.

Recommendations

Cites work

Cited in

(8)

This page was built for publication: Cut-edges and regular factors in regular graphs of odd degree