×

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
PDF BibTeX Cite
Full Text: DOI