Orthogonally Resolvable Matching Designs

Abstract

An Orthogonally resolvable Matching Design OMD$(n,k)$ is a partition of the edges the complete graph $K_n$ into matchings of size $k$, called blocks, such that the blocks can be resolved in two different ways. Such a design can be represented as a square array whose cells are either empty or contain a matching of size $k$, where every vertex appears exactly once in each row and column. In this paper we show that an OMD$(n.k)$ exists if and only if $n\equiv 0(\mathrm{mod}2k)$ except when $k=1$ and $n=4$ or $6$.