›› 2014, Vol. 53 ›› Issue (5): 54-58.

Previous Articles     Next Articles

The Number of Perfect Matchings in Two Types of 3-Regular Graph

TANG Baoxiang1, REN Han2   

  1. 1. School of Mathematics and Statistics, Tianshui Normal University,Tianshui 741001, China;
    2. Department of Mathematics, East China Normal University,Shanghai 200062, China
  • Received:2013-12-12 Online:2014-09-25 Published:2014-09-25

Abstract: It's an important application for perfect matching counting theories in quantum chemistry, crystal physics and computer science. The research for perfect matching counting theories has a quite important theoretical value and realistic meanings. But the counting problem of perfect matching for general graphs has been proved to be NP—hard. Lovász and Plummer proposed a conjecture on this problem: every 2-edge-connected cubic graph has at least exponential perfect matchings. By applying differentiation, summation and re-nested recursive calculation, several counting formulas of the perfect matching for two specific types of graphs are given. And the results indicate that the conjecture of Lovász and Plummer is true in the case of these two types of graphs.

Key words: perfect matching, linear recurrence relation, characteristic equation

CLC Number: