Séminaire Lotharingien de Combinatoire, B74e (2017), 10 pp.

Roy H. Jennings

Geodesics in a Graph of Perfect Matchings

Abstract. Let Pm be the graph on the set of perfect matchings in the complete graph K2m, where two perfect matchings are connected by an edge if their symmetric difference is a cycle of length four. This paper studies geodesics in Pm. The diameter of Pm, 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 mm-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 Sm. An explicit formula for the number of geodesics between any two matchings in Pm is also given. Let Mm 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 Pm. Mm is an induced subgraph of Pm, and it is shown that Mm has exactly one pair of antipodes having the maximal number mm-2 of geodesics between them.

Received: July 9, 2015. Revised: February 16, 2017. Accepted: May 1, 2017.

The following versions are available: