Search

A decomposition of a multigraph G is a partition of its edges into subgraphs G (1) , ... , G (k). It is called an r -factorization if every G (i) is r -regular and spanning. If G is a subgraph of H , a decomposition of G is said to be enclosed in a decomposition of H if, for every 1 ≤ i ≤ k , G (i) is a subgraph of H (i). Feghali and Johnson gave necessary and sufficient conditions for a given decomposition of λ K n to be enclosed in some 2-edge-connected r -factorization of μ K m for some range of values for the parameters n , m , λ , μ , r : r = 2 , μ > λ and either m ≥ 2 n − 1 , or m = 2 n − 2 and μ = 2 and λ = 1 , or n = 3 and m = 4. We generalize their result to every r ≥ 2 and m ≥ 2 n − 2. We also give some sufficient conditions for enclosing a given decomposition of λ K n in some 2-edge-connected r -factorization of μ K m for every r ≥ 3 and m > (2 − C) n , where C is a constant that depends only on r , λ and μ. [ABSTRACT FROM AUTHOR]