✦ LIBER ✦

Perfect matchings and ears in elementary bipartite graphs

✍ Scribed by Pierre Hansen; Fuji Zhang; Maolin Zheng

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 386 KB
Volume: 176
Category: Article
ISSN: 0012-365X
DOI: 10.1016/s0012-365x(96)00291-9

No coin nor oath required. For personal study only.

✦ Synopsis

We give lower and upper bounds for the number of reducible ears as well as upper bounds for the number of perfect matchings in an elementary bipartite graph. An application to chemical graphs is also discussed. In addition, a method to construct all minimal elementary bipartite graphs is described.

📜 SIMILAR VOLUMES

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

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

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

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

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

Induced matchings in bipartite graphs

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