Enumerating Perfect Matchings in n-Cubes

摘要

The perfect matchings in the n-cube have earlier been enumerated for n ≤ 6. A dynamic programming approach is here used to obtain the total number of perfect matchings in the 7-cube, which is 391689 748 492 473 664 721 077 609 089. The number of equivalence classes of perfect matchings is further shown to be 336 in the 5-cube, 356788059 in the 6-cube and 607 158046 495 120 886 820 621 in the 7-cube. The techniques used can be generalized to arbitrary bipartite and general graphs.