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: