A note on the number of perfect matchings of bipartite graphs

作者：Zhang FJ; Zhang HP

来源：Discrete Applied Mathematics, 1997, 73(3): 275-282.

Let G be a bipartite graph with 2n vertices, A its adjacency matrix and K the number of perfect matchings. For plane bipartite graphs each interior face of which is surrounded by a circuit of length 4s+2, s is an element of {1,2,...}, an elegant formula, i.e. detA = (-1)K-n(2), had been rigorously proved by Cvetkovic et al. (1982). For general bipartite graphs, this note contains a necessary and sufficient condition for the above relation to hold. A fast algorithm to check if a plane bipartite graph has such a relation is given.

• 单位
  兰州大学