# zbMATH — the first resource for mathematics

Graphs of non-crossing perfect matchings. (English) Zbl 1009.05110
Summary: Let $$P_n$$ be a set of $$n=2m$$ points that are the vertices of a convex polygon, and let $$\mathcal M_m$$ be the graph having as vertices all the perfect matchings in the point set $$P_n$$ whose edges are straight line segments and do not cross, and edges joining two perfect matchings $$M_1$$ and $$M_2$$ if $$M_2 = M_1 - (a,b) - (c,d) + (a,d) + (b,c)$$ for some points $$a,b,c,d$$ of $$P_n$$. We prove the following results about $$\mathcal M_m$$: its diameter is $$m-1$$; it is bipartite for every $$m$$; the connectivity is equal to $$m-1$$; it has no Hamilton path for $$m$$ odd, $$m>3$$; and finally it has a Hamilton cycle for every $$m$$ even, $$m\geq 4$$.

##### MSC:
 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) 05C45 Eulerian and Hamiltonian graphs 05C40 Connectivity
##### Keywords:
perfect matching; non-crossing configuration; Gray code
Full Text: