Switching in one-factorisations of complete graphs

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

¹Monash University

The electronic journal of combinatorics, Tome 21 (2014) no. 2

Résumé

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.

Détail

DOI : 10.37236/3606

Classification : 05C70, 05B15, 05C60, 05C51
Mots-clés : one-factorisation, switching, perfect one-factorisation, Hamiltonian Latin square, atomic Latin square, group divisible design