Jennings, Roy H.

Geodesics in a graph of perfect matchings

Sémin. Lothar. Comb. 74, B74e, 10 p. (2017)

Summary

Summary: Let $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 $P_{m}$. The diameter of $P_{m}$, as well as the eccentricity of each vertex, are shown to be $m-1$. Two proofs 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 $P_{m}$ is also given. Let $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 $P_{m}. M_{m}$ is an induced subgraph of $P_{m}$, and it is shown that $M_{m}$ has exactly one pair of antipodes having the maximal number $m^{m-2}$ of geodesics between them.

Downloads