Enclosings of Decompositions of Complete Multigraphs in 2-Factorizations

Abstract

Let $k$, $\lambda$ and $\mu$ be positive integers. A decomposition of a multigraph $\lambda G$ into edge-disjoint subgraphs $G_1,\dots ,G_k$ is said to be \emph{enclosed} by a decomposition of a multigraph $\mu H$ into edge-disjoint subgraphs $H_1,\dots ,H_k$ if $\mu >\lambda$ and $G_i$ is a subgraph of $H_i$, $1\le i\le 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\ge 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\ge n-1$, or $\mu >\lambda$, $n=3$ and $m=1$, or $\mu =2$, $\lambda =1$ and $m=n-2$.

arXiv comment19 pages