𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The rotation graphs of perfect matchings of plane bipartite graphs

✍ Scribed by Heping Zhang; Fuji Zhang

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

No coin nor oath required. For personal study only.

✦ Synopsis

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 bipartite graphs. As an immediate result, we describe a one-to-one correspondence between MPAC systems and perfect matchings in G.

πŸ“œ SIMILAR VOLUMES

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

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

Let G be a plane bipartite graph. The Z-transformation graph Z(G) and its orientation Z(G) on the maximum matchings of G are deΓΏned. If G has a perfect matching, Z(G) and Z(G) are the usual Z-transformation graph and digraph. If G has neither isolated vertices nor perfect matching, then Z(G) is not

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

Combinatorics of perfect matchings in pl
Combinatorics of perfect matchings in plane bipartite graphs and application to tilings
✍ J.C. Fournier πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 737 KB

Let G be a plane bipartite graph which admits a perfect matching and with distinguished faces called holes. Let MG denote the perfect matchings graph: its vertices are the perfect matchings of G, two of them being joined by an edge, if and only if they di er only on an alternating cycle bounding a f