Extending Matchings to \(2\)-Factors

R.E.L. Aldred1, Derek Holton1, John Sheehan2
1Department of Mathematics and Statistics University of Otago, P.O. Box 56, Dunedin, New Zealand.
2Department of Mathematical Sciences University of Aberdeen, King’s College, Aberdeen AB24 3UE, U.K.

Abstract

Let \( G \) be a finite \( 4 \)-regular cyclically \( 2k \)-edge-connected simple graph for some integer \( k \geq 1 \). Let \( E(k) \) be a set of \( k \) independent edges in \( G \) and \( (E_1, E_2) \) be a partition of \( E(k) \). We consider when there exists a \( 2 \)-factor in \( G \) which excludes all edges of \( E_1 \), and includes all the edges of \( E_2 \). A complete characterization is provided.