𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On maximum induced matchings in bipartite graphs

✍ Scribed by V.V. Lozin

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
75 KB
Volume
81
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Induced matchings in bipartite graphs
Induced matchings in bipartite graphs
✍ R.J. Faudree; A. GyΓ‘rfas; R.H. Schelp; Zs. Tuza πŸ“‚ Article πŸ“… 1989 πŸ› Elsevier Science 🌐 English βš– 454 KB
Maximum induced matchings in graphs
Maximum induced matchings in graphs
✍ Jiping Liu; Huishan Zhou πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 218 KB

We provide a formula for the number of edges of a maximum induced matching in a graph. As applications, we give some structural properties of (k + 1 )K2-free graphs, construct all 2K2-free graphs, and count the number of labeled 2K2-free connected bipartite graphs.

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

Local maximum stable sets in bipartite g
Local maximum stable sets in bipartite graphs with uniquely restricted maximum matchings
✍ Vadim E. Levit; Eugen Mandrescu πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 233 KB

A maximum stable set in a graph G is a stable set of maximum size. S is a local maximum stable set of G, and we write S ∈ (G), if S is a maximum stable set of the subgraph spanned by S βˆͺ N (S), where N (S) is the neighborhood of S. A matching M is uniquely restricted if its saturated vertices induce