Geodesics in a Graph of Perfect Matchings

Abstract

Let ${\mathcal{P}}_m$ be the graph on the set of perfect matchings in the complete graph $K_{2m}$, where two perfect matchings are connected by an edge if their symmetric difference is a cycle of length four. This paper studies geodesics in ${\mathcal{P}}_m$. The diameter of ${\mathcal{P}}_m$, as well as the eccentricity of each vertex, are shown to be $m-1$. Two proof are given to show that the number of geodesics between any two antipodes is $m^{m-2}$. The first is a direct proof via a recursive formula, and the second is via reduction to the number of minimal factorizations of a given $m$-cycle in the symmetric group $S_m$. An explicit formula for the number of geodesics between any two matchings in ${\mathcal{P}}_m$ is also given. Let ${\mathcal{M}}_m$ be the graph on the set of non-crossing perfect matchings of $2m$ labeled points on a circle with the same adjacency condition as in ${\mathcal{P}}_m$. ${\mathcal{M}}_m$ is an induced subgraph of ${\mathcal{P}}_m$, and it is shown that ${\mathcal{M}}_m$ has exactly one pair of antipodes having the maximal number ($m^{m-2}$) of geodesics between them.

Cited by in corpus (2)

• Flip Graphs, Yoke Graphs and Diameter
• On the flip graphs on perfect matchings of complete graphs and signed reversal graphs