Perfect Matchings of Cellular Graphs
Perfect Matchings of Cellular Graphs
复制标题
DOI：
10.1023/a:1022408900061
复制
发表时间：
1996-04
影响因子：
0.8
通讯作者：
Mihai Ciucu
中科院分区：
文献类型：
--
作者：
Mihai Ciucu
我们介绍了一个家庭的图，称为细胞，并考虑枚举他们的完美匹配的问题。我们证明了一个细胞图的完美匹配数等于某个子图的完美匹配数的2次方，这个子图称为图的核。作为一个特例，给出了由Elkies，Kuperberg，Larsen和Propp提出的阿兹特克有序钻石图恰好有2n（n+1）/2个完美匹配的新证明.作为进一步的应用，我们证明了一个递归的一些分区索引的细胞图的完美匹配，我们列举了两个其他家庭的图形称为阿兹特克矩形和阿兹特克三角形的完美匹配。
We introduce a family of graphs, called cellular, and consider the problem of enumerating their perfect matchings. We prove that the number of perfect matchings of a cellular graph equals a power of 2 times the number of perfect matchings of a certain subgraph, called the core of the graph. This yields, as a special case, a new proof of the fact that the Aztec diamond graph of ordernintroduced by Elkies, Kuperberg, Larsen and Propp has exactly 2n(n+1)/2perfect matchings. As further applications, we prove a recurrence for the number of perfect matchings of certain cellular graphs indexed by partitions, and we enumerate the perfect matchings of two other families of graphs called Aztec rectangles and Aztec triangles.