The number of perfect matchings in a hypercube (Q580373)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The number of perfect matchings in a hypercube |
scientific article |
Statements
The number of perfect matchings in a hypercube (English)
0 references
1988
0 references
A perfect matching or a 1-factor of a graph G is a spanning subgraph that is regular of degree one. Hence a perfect matching is a set of independent edges which matches all the nodes of G in pairs. Thus in a hypercube parallel processor, the number of perfect matchings evaluates the number of different ways that all the processors can pairwise exchange information in parallel. Making use of matrices and their permanents one can write a straightforward formula which we evaluate for \(n\leq 5\).
0 references
perfect matching
0 references
1-factor
0 references
hypercube
0 references