Invariants and neighborhood structures for 1-factorizations of complete graphs

Abstract

A 1-factorization is a partition of the edge set of a graph into perfect matchings. The concept of 1-factorization is of great interest due to its applications in modeling sports tournaments. Two 1-factorizations are said to be isomorphic (belong to the same isomorphism class) if there exists a bijection between their sets of vertices that transforms one into the other. The non-isomorphic 1-factorization search space is a graph in which each isomorphism class is represented by a vertex and each edge that connects the vertices $\mathcal{F}_a$ and $\mathcal{F}_b$ corresponds to a move in a neighborhood structure, which from a 1-factorization isomorphic to $\mathcal{F}_a$ generates a 1-factorization isomorphic to $\mathcal{F}_b$. An invariant of a 1-factorization is a property that depends only on its structure such that isomorphic 1-factorizations are guaranteed to have equal invariant values. An invariant is complete when any two non-isomorphic 1-factorizations have distinct invariant values. This thesis reviews seven invariants used to distinguish non-isomorphic 1-factorizations of $K_{2n}$ (complete graph with an even number of vertices). Additionally, considering that the invariants available in the literature are not complete, we propose two new ones, denoted lantern profiles and even-size bichromatic chains. The invariants are compared regarding their sizes and calculation time complexity. Furthermore, we conduct computational experiments to assess their ability to distinguish non-isomorphic 1-factorizations. To accomplish that we use the sets of non-isomorphic 1-factorizations of $K_{10}$ and $K_{12}$, as well as the sets of non-isomorphic perfect 1-factorizations of $K_{14}$ and $K_{16}$. We also consider algorithmic and computational aspects for exploring the generalized partial team swap (GPTS) neighborhood, a neighborhood structure for round-robin sports scheduling problems recently proposed in the literature. In this regard, we present a framework to explore the GPTS neighborhood. Finally, a discussion is presented on how this neighborhood structure increases the connectivity of the search space defined by non-isomorphic 1-factorizations of $K_{2n}$ (for $8 \le 2n \le 12$) when compared to other neighborhood structures.