✦ LIBER ✦

The number of perfect matchings in a hypercube

✍ Scribed by Niall Graham; Frank Harary

Publisher: Elsevier Science
Year: 1988
Tongue: English
Weight: 243 KB
Volume: 1
Category: Article
ISSN: 0893-9659
DOI: 10.1016/0893-9659(88)90173-5

No coin nor oath required. For personal study only.

✦ Synopsis

A perfect matching or a l-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 < 5.

📜 SIMILAR VOLUMES

Perfect matchings of a graph

✍ Ian Anderson 📂 Article 📅 1971 🏛 Elsevier Science 🌐 English ⚖ 179 KB

On the galactic number of a hypercube

✍ Michael Fellows; Mark Hoover; Frank Harary 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 298 KB

A galaxy is a union of vertex disjoint stars. The galactic number of a graph is the minimum number of galaxies which partition the edge set. The galactic number of complete graphs is determined. This result is used to give bounds on the galactic number of binary cube graphs. The problem of determini

How to calculate the number of perfect m

How to calculate the number of perfect matchings in finite sections of certain infinite plane graphs

✍ Horst Sachs 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 341 KB

Finding all the perfect matchings in bip

Finding all the perfect matchings in bipartite graphs

✍ K. Fukuda; T. Matsui 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 283 KB

Special parity of perfect matchings in b

Special parity of perfect matchings in bipartite graphs

✍ Ron Aharoni; Rachel Manber; Bronislaw Wajnryb 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 527 KB

Let G be a bipartite graph in which every edge belongs to some perfect matching, and let D be a subset of its edge set. It is shown that M fl D has the same parity for every perfect matching M if and only if D is a cut, and equivalently if and only. if (G, D) is a balanced signed-graph. This gives n

The rainbow number of matchings in regul

The rainbow number of matchings in regular bipartite graphs

✍ Xueliang Li; Zhixia Xu 📂 Article 📅 2009 🏛 Elsevier Science 🌐 English ⚖ 386 KB

Given a graph G and a subgraph H of G, let rb(G, H) be the minimum number r for which any edge-coloring of G with r colors has a rainbow subgraph H. The number rb(G, H) is called the rainbow number of H with respect to G. Denote as mK 2 a matching of size m and as B n,k the set of all the k-regular