Graphs of non-crossing perfect matchings
Graphs of non-crossing perfect matchings
复制标题
DOI：
10.1007/s003730200038
复制
发表时间：
2002-01-01
影响因子：
0.7
通讯作者：
Noy, M
中科院分区：
文献类型：
--
作者：
Hernando, C;Furtado, F;Noy, M
设P-n是凸多边形顶点的n=2m个点的集合，H-m是这样一个图，其顶点是点集P中的所有完美匹配，其边是直线段且不相交，且当M-2=M-1-(a，b)-(c，d)+(a，d)+(b，c)时，两个完美匹配44的边连接在一起。我们证明了关于H-m的下列结果：它的直径是m-1；它对每一个m都是二部的；它的连通度等于m-1；它对m奇数m>；3没有哈密尔顿路；最后它对偶数m中的每一个都有哈密尔顿圈。
Let P-n be a set of n = 2m points that are the vertices of a convex polygon, and let H-m be the graph having as vertices all the perfect matchings in the point set P, whose edges are straight line segments and do not cross, and edges joining two perfect matchings 44, mid 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 H-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 in even, m greater than or equal to 4.