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 \geq 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.