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\).

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C45 Eulerian and Hamiltonian graphs
05C40 Connectivity
PDF BibTeX Cite
Full Text: DOI