Geodesics in a graph of perfect matchings

MaRDI QIDQ526302zbMATH OpenFDO

Authors Roy H. Jennings

Publication date 10 May 2017

Published in Séminaire Lotharingien de Combinatoire (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1306.3611, http://www.emis.de/journals/SLC/wpapers/s74jenn.html

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

zbMATH Keywords

diametereccentricity of vertices

Mathematics Subject Classification ID

Distance in graphs (05C12) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Let $mathscr{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 $mathscr{P}_m$. The diameter of $mathscr{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 $mathscr{P}_m$ is also given. Let $mathscr{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 $mathscr{P}_m$. $mathscr{M}_m$ is an induced subgraph of $mathscr{P}_m$, and it is shown that $mathscr{M}_m$ has exactly one pair of antipodes having the maximal number ($m^{m-2}$) of geodesics between them.

Recommendations

• Graphs of non-crossing perfect matchings
• Compatible geometric matchings
• The Monotonic Diameter of the Perfect 2-matching Polytope
• On flips in planar matchings
• On the upper bounds of the numbers of perfect matchings in graphs with given parameters

Cited in

(4)

• Flip graphs, Yoke graphs and diameter
• Plane Geodesic Spanning Trees, Hamiltonian Cycles, and Perfect Matchings in a Simple Polygon
• Graphs of non-crossing perfect matchings
• On the flip graphs on perfect matchings of complete graphs and signed reversal graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q526302)