Multidecomposition of $K_n–F$ into Graph-Pairs of Order $5$ where $F$ is a Hamilton Cycle or an (almost) $1$-Factor

Abstract

A graph-pair of order $t$ is two non-isomorphic graphs $G$ and $H$ on $t$ non-isolated vertices for which $G\cup H\cong K_t$ for some integer $t\ge 4$. Given a graph-pair $(G,H)$, we say $(G,H)$ divides some graph $K$ if the edges of $K$ can be partitioned into copies of $G$ and $H$ with at least one copy of $G$ and at least one copy of $H$. We will refer to this partition as a $(G,H)$-$multidecomposition$ of $K$.

In this paper, we consider the existence of multidecompositions of $K_n–F$ into graph-pairs of order $5$ where $F$ is a Hamiltonian cycle or (almost) $1$-factor.