Enclosings of Decompositions of Complete Multigraphs in 2-Factorizations

Carl Feghali, Matthew Johnson

Published 2016-08-24Version 1

Let $k$, $\lambda$ and $\mu$ be positive integers. A decomposition of a multigraph $ \lambda G$ into edge-disjoint subgraphs $G_1, \ldots , G_k$ is said to be \emph{enclosed} by a decomposition of a multigraph $\mu H$ into edge-disjoint subgraphs $H_1, \ldots , H_k$ if $\mu > \lambda$ and $G_i$ is a subgraph of $H_i$, $1 \leq i \leq k$. In this paper we initiate the study of when a decomposition can be enclosed by a decomposition that consists of spanning subgraphs. A decomposition of a graph is a 2-factorization if each subgraph is 2-regular and is Hamiltonian if each subgraph is a Hamiltonian cycle. Let $n$ and $m$ be positive integers. We give necessary and sufficient conditions for enclosing a decomposition of $\lambda K_n$ in a $2$-factorization of $\mu K_{n+m}$ whenever $\mu>\lambda$ and $m \geq n-2$. We also give necessary and sufficient conditions for enclosing a decomposition of $\lambda K_n$ in a Hamiltonian decomposition of $\mu K_{n+m}$ whenever $\mu > \lambda$ and $m \geq n-1$, or $\mu > \lambda$, $n=3$ and $m=1$, or $\mu = 2$, $\lambda=1$ and $m=n-2$.