×

Three types of nested recursive methods for finding counting formulas of the number of perfect matchings. (Chinese. English summary) Zbl 1424.05156

Summary: The perfect matching counting problem of a graph has been proven to be NP-hard, so to get the number of a perfectly matched general graph is very difficult. The issue has important applications in quantum chemistry, crystal physics and computer science. Research on this issue has very important theoretical and practical significance. The counting formula of the perfect matching for graphs \(2 - n{D_4}\), \(2 - n{C_{6, 3}}\) and \(3 - n{C_6}\) is given by applying differentiation, summation and re-recursion. The number of all perfect matchings of many graphs can be calculated by this method. The given method is also able to get the possibility that the perfect graphs match with the counting of all perfect matching.

MSC:

05C30 Enumeration in graph theory
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C90 Applications of graph theory
92E10 Molecular structure (graph-theoretic methods, methods of differential topology, etc.)
PDFBibTeX XMLCite
Full Text: DOI