𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A note on the number of perfect matchings of bipartite graphs

✍ Scribed by Zhang Fuji; Zhang Heping

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
484 KB
Volume
73
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

Let G be a bipartite graph with 2n vertices, A its adjacency matrix and K the number of perfect matchings. For plane bipartite graphs each interior face of which is surrounded by a circuit of length 4s + 2, s E { 1,2,. . .}, an elegant formula, i.e. det A = (-1 )nK2, had been rigorously proved by CvetkoviC et al. (1982). For general bipartite graphs, this note contains a necessary and sufficient condition for the above relation to hold. A fast algorithm to check if a plane bipartite graph has such a relation is given.

πŸ“œ SIMILAR VOLUMES

The rotation graphs of perfect matchings
The rotation graphs of perfect matchings of plane bipartite graphs
✍ Heping Zhang; Fuji Zhang πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 517 KB

In the present paper, the minimal proper alternating cycle (MPAC) rotation graph R(G) of perfect matchings of a plane bipartite graph G is defined. We show that an MPAC rotation graph R(G) of G is a directed rooted tree, and thus extend such a result for generalized polyhex graphs to arbitrary plane

Z-transformation graphs of perfect match
Z-transformation graphs of perfect matchings of plane bipartite graphs
✍ Heping Zhang; Fuji Zhang; Haiyuan Yao πŸ“‚ Article πŸ“… 2004 πŸ› Elsevier Science 🌐 English βš– 343 KB

Let G be a plane bipartite graph with at least two perfect matchings. The Z-transformation graph, ZF (G), of G with respect to a speciΓΏc set F of faces is deΓΏned as a graph on the perfect matchings of G such that two perfect matchings M1 and M2 are adjacent provided M1 and M2 di er only in a cycle t

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