k-Factors Containing and Avoiding Specified Sets of Edges

Abstract

Let r, k be integers with k ≥ 1 and r ≥ 2k, and let Go be an r-regular r-edge-connected graph with k|V(G_o)| even. Let A, B be subsets of E(G_o) with A∩B = such that |A| and |B| satisfy one of the following three conditions: (I) k/2 < |A| ≤ k and |A| + |B| ≤ k; (II) 1 ≤ |A| ≤ k/2 and |A| + |B| ≤ [r/2]; or (III) |A| = 0 and |B| ≤ r - k. Under these assumptions, we show that G_o has a k-factor F with E(F)⊇A and E(F)∩B = , unless (G_o; A, B) belongs to an exceptional family of triples.

Keywords:

• graph
• regular factor

2000 Mathematics Subject Classification:

• 05C70