Geodesics in a graph of perfect matchings

Abstract: Let

m a t h s c r P_{m}

be the graph on the set of perfect matchings in the complete graph

K_{2 m}

, where two perfect matchings are connected by an edge if their symmetric difference is a cycle of length four. This paper studies geodesics in

m a t h s c r P_{m}

. The diameter of

m a t h s c r 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

m a t h s c r P_{m}

is also given. Let

m a t h s c r 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

m a t h s c r P_{m}

.

m a t h s c r M_{m}

is an induced subgraph of

m a t h s c r P_{m}

, and it is shown that

m a t h s c r M_{m}

has exactly one pair of antipodes having the maximal number (

m^{m - 2}

) of geodesics between them.

Full work available at URL: https://arxiv.org/abs/1306.3611

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

Cited In (4)

This page was built for publication: Geodesics in a graph of perfect matchings