Enclosings of Decompositions of Complete Multigraphs in $2$-Edge-Connected $r$-Factorizations

Abstract

A decomposition of a multigraph $G$ is a partition of its edges into subgraphs $G(1),\dots ,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\le i\le k$, $G(i)$ is a subgraph of $H(i)$. Feghali and Johnson gave necessary and sufficient conditions for a given decomposition of $\lambda K_n$ to be enclosed in some $2$-edge-connected $r$-factorization of $\mu K_m$ for some range of values for the parameters $n$, $m$, $\lambda$, $\mu$, $r$: $r=2$, $\mu >\lambda$ and either $m\ge 2n-1$, or $m=2n-2$ and $\mu =2$ and $\lambda =1$, or $n=3$ and $m=4$. We generalize their result to every $r\ge 2$ and $m\ge 2n-2$. We also give some sufficient conditions for enclosing a given decomposition of $\lambda K_n$ in some $2$-edge-connected $r$-factorization of $\mu K_m$ for every $r\ge 3$ and $m=(2-C)n$, where $C$ is a constant that depends only on $r$, $\lambda$ and~$\mu$.

17 pages; fixed the proof of Theorem 1.4 and other minor changes