Enumeration of perfect matchings of a type of Cartesian products of graphs |
| |
Authors: | Weigen Yan Fuji Zhang |
| |
Institution: | a School of Sciences, Jimei University, Xiamen 361021, PR China b Department of Mathematics, Xiamen University, Xiamen 361005, PR China |
| |
Abstract: | Let G be a graph and let Pm(G) denote the number of perfect matchings of G.We denote the path with m vertices by Pm and the Cartesian product of graphs G and H by G×H. In this paper, as the continuance of our paper W. Yan, F. Zhang, Enumeration of perfect matchings of graphs with reflective symmetry by Pfaffians, Adv. Appl. Math. 32 (2004) 175-188], we enumerate perfect matchings in a type of Cartesian products of graphs by the Pfaffian method, which was discovered by Kasteleyn. Here are some of our results:1. Let T be a tree and let Cn denote the cycle with n vertices. Then Pm(C4×T)=∏(2+α2), where the product ranges over all eigenvalues α of T. Moreover, we prove that Pm(C4×T) is always a square or double a square.2. Let T be a tree. Then Pm(P4×T)=∏(1+3α2+α4), where the product ranges over all non-negative eigenvalues α of T.3. Let T be a tree with a perfect matching. Then Pm(P3×T)=∏(2+α2), where the product ranges over all positive eigenvalues α of T. Moreover, we prove that Pm(C4×T)=Pm(P3×T)]2. |
| |
Keywords: | Perfect matching Pfaffian orientation Skew adjacency matrix Cartesian product Bipartite graph Nice cycle |
本文献已被 ScienceDirect 等数据库收录! |
|