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

# Roy H. Jennings

# Geodesics in a Graph of Perfect Matchings

**Abstract.**
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 2*m* 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.

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

The following versions are available: