Minimal defining sets of 1-factorizations of complete graphs

Abstract

A defining set of a 1-factorization of a graph G is a set of partial 1-factors of G which may be completed to a unique 1-factorization of G. In this paper we construct minimal defining sets of size (n-4)(n+2)/4 in the 1-factorizations GK_n (as defined in [1]) of K_n for each even n ≥ 4. Our construction exploits the well-known equivalence between 1-factorizations and unipotent, symmetric Latin squares.