Further results on enumeration of perfect matchings of Cartesian product graphs

Abstract

Counting perfect matchings is an interesting and challenging combinatorial task. It has important applications in statistical physics and chemistry. As the general problem is #P-complete, it is usually tackled by randomized heuristics and approximation schemes. Let GG and HH be two graphs. Denote by G×HG\times H the Cartesian product of graphs GG and HH. The number of perfect matchings of some types of Cartesian product G×HG\times H is investigated by the Pfaffian method, where G≅P2G\cong {P}_{2}, P3{P}_{3}, P4{P}_{4} or C4{C}_{4}, and H≅TH\cong T or HH is a non-bipartite graph with a unique cycle. In this article, we construct a Pfaffian orientation of the graph G×P2G\times {P}_{2}, where GG is a non-bipartite graph with kk odd cycles. We obtain the counting formula on the number of perfect matchings of G×P2G\times {P}_{2}.

Keywords

• pfaffian orientation
• perfect matching
• skew adjacency matrix
• cartesian product
• 05a15
• 05c30
• 05c50
• 05c70