𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Graphs with independent perfect matchings

✍ Scribed by Marcelo H. de Carvalho; Cláudio L. Lucchesi; U. S. R. Murty

Publisher
John Wiley and Sons
Year
2004
Tongue
English
Weight
241 KB
Volume
48
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

A graph with at least two vertices is matching covered if it is connected and each edge lies in some perfect matching. A matching covered graph G is extremal if the number of perfect matchings of G is equal to the dimension of the lattice spanned by the set of incidence

📜 SIMILAR VOLUMES

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

Maximal matchings in graphs with large n
Maximal matchings in graphs with large neighborhoods of independent vertices
✍ I. Rinsma; C. H. C. Little; D. R. Woodall 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 174 KB

## Abstract We obtain lower bounds on the size of a maximum matching in a graph satisfying the condition |__N(X)__| ≥ __s__ for every independent set __X__ of __m__ vertices, thus generalizing results of Faudree, Gould, Jacobson, and Schelp for the case __m__ = 2.

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