Switching in One-Factorisations of Complete Graphs

Petteri Kaski, André de Souza Medeiros, Patric R.J. Östergård, Ian M. Wanless


We define two types of switchings between one-factorisations of complete graphs, called factor-switching and vertex-switching. For each switching operation and for each $n\le 12$, we build a switching graph that records the transformations between isomorphism classes of one-factorisations of $K_{n}$.  We establish various parameters of our switching graphs, including order, size, degree sequence, clique number and the radius of each component.

As well as computing data for $n\le12$, we demonstrate several properties that hold for one-factorisations of $K_{n}$ for general $n$. We show that such factorisations have a parity which is not changed by factor-switching, and this leads to disconnected switching graphs. We also characterise the isolated vertices that arise from an absence of switchings. For factor-switching the isolated vertices are perfect one-factorisations, while for vertex-switching the isolated vertices are closely related to atomic Latin squares.


one-factorisation; switching; perfect one-factorisation; Hamiltonian Latin square; atomic Latin square; group divisible design

Full Text: