Fair 1-Factorizations and Fair Holey 1-Factorizations of Complete Multipartite Graphs

Abstract

A k-factor of a graph G is a k-regular spanning subgraph of G. A k-factorization is a partition of E(G) into k-factors. Let K(n, p) be the complete multipartite graph with p parts, each of size n. If $V_{1},\ldots , V_{p}$ are the p parts of V(K(n, p)), then a holey k -factor of deficiency $V_{i}$ of K(n, p) is a k-factor of $K(n,p)-V_{i}$ for some i satisfying $1\le i \le p$. Hence a holey k -factorization is a set of holey k-factors whose edges partition E(K(n, p)). Representing each (holey) k-factor as a color class in an edge-coloring, a (holey) k-factorization of K(n, p) is said to be fair if between each pair of parts the color classes have size within one of each other (so the edges are shared “evenly” among the permitted (holey) factors). In this paper the existence of fair 1-factorizations of K(n, p) is completely settled, as is the existence of fair holey 1-factorizations of K(n, p). The latter result can be used to provide a new construction for symmetric quasigroups of order np with holes of size n. Such quasigroups have the additional property that the permitted symbols are shared as evenly as possible among the cells in each $n \times n$ “box”. These quasigroups are in some sense as far from frames produced by direct products as possible.