Graphs of Non-Crossing Perfect Matchings |
| |
Authors: | C Hernando F Hurtado Marc Noy |
| |
Institution: | (1) Department de Matemàtica Aplicada I, Universitat Politècnica de Catalunya, Diagonal 647, 08028 Barcelona, Spain. e-mail: hernando@ma1.upc.es, ES;(2) Department de Matemàtica Aplicada II, Universitat Politècnica de Catalunya, Pau Gargallo 5, 08028 Barcelona, Spain. e-mail: hurtado, ES;(3) Department de Matemàtica Aplicada II, Universitat Politècnica de Catalunya, Pau Gargallo 5, 08028 Barcelona, Spain. e-mail: noy@ma2.upc.es, ES |
| |
Abstract: | Let P
n
be a set of n=2m points that are the vertices of a convex polygon, and let ℳ
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 ℳ
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≥4.
Received: October 10, 2000 Final version received: January 17, 2002
RID="*"
ID="*" Partially supported by Proyecto DGES-MEC-PB98-0933
Acknowledgments. We are grateful to the referees for comments that helped to improve the presentation of the paper. |
| |
Keywords: | , ,Perfect matching, Non-crossing configuration, Gray code |
本文献已被 SpringerLink 等数据库收录! |
|