✦ LIBER ✦

Special parity of perfect matchings in bipartite graphs

✍ Scribed by Ron Aharoni; Rachel Manber; Bronislaw Wajnryb

Publisher: Elsevier Science
Year: 1990
Tongue: English
Weight: 527 KB
Volume: 79
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(90)90330-k

No coin nor oath required. For personal study only.

✦ Synopsis

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 necessary and sufficient conditions on the sign pattern of an n x n real matrix under which all nonzero terms in its permanent expansion have the same sign.

📜 SIMILAR VOLUMES

Finding all minimum-cost perfect matchin

Finding all minimum-cost perfect matchings in Bipartite graphs

✍ Komei Fukuda; Tomomi Matsui 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 401 KB

Induced matchings in bipartite graphs

✍ R.J. Faudree; A. Gyárfas; R.H. Schelp; Zs. Tuza 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 454 KB

Transversal hypergraphs to perfect match

Transversal hypergraphs to perfect matchings in bipartite graphs: Characterization and generation algorithms

✍ Endre Boros; Khaled Elbassioni; Vladimir Gurvich 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 285 KB

A minimal blocker in a bipartite graph G is a minimal set of edges the removal of which leaves no perfect matching in G. We give an explicit characterization of the minimal blockers of a bipartite graph G. This result allows us to obtain a polynomial delay algorithm for finding all minimal blockers

Maximum matchings in bipartite graphs vi

Maximum matchings in bipartite graphs via strong spanning trees

✍ M. L. Balinski; J. Gonzalez 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 692 KB

Enumeration of Perfect Matchings in Grap

Enumeration of Perfect Matchings in Graphs with Reflective Symmetry

✍ Mihai Ciucu 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 759 KB

A plane graph is called symmetric if it is invariant under the reflection across some straight line. We prove a result that expresses the number of perfect matchings of a large class of symmetric graphs in terms of the product of the number of matchings of two subgraphs. When the graph is also centr

Stable Set Bonding in Perfect Graphs and

Stable Set Bonding in Perfect Graphs and Parity Graphs

✍ D.G. Corneil; J. Fonlupt 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 486 KB