Combinatorics of perfect matchings in plane bipartite graphs and application to tilings

被引：16

作者：

Fournier, JC ^{[1
]}

机构：

[1] Univ Paris 12 Creteil, Equipe Combinatoire, CNRS Paris 6, Paris, France

来源：

THEORETICAL COMPUTER SCIENCE | 2003年 / 303卷 / 2-3期

关键词：

D O I：

10.1016/S0304-3975(02)00496-6

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Let G be a plane bipartite graph which admits a perfect matching and with distinguished faces called holes. Let M-G denote the perfect matchings graph: its vertices are the perfect matchings of G, two of them being joined by an edge, if and only if they differ only on an alternating cycle bounding a face which is not a hole. We solve the following problem: Find a criterion for two perfect matchings of G to belong to the same connected component of M-g and in particular determine in which case M-g is connected. The motivation of this work is a result on tilings of Saldanha et al. (Comput. Geom. 14 (1995) 207). (C) 2002 Elsevier Science B.V. All rights reserved.

引用

页码：333 / 351

页数：19