𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Maximum induced matchings in graphs

✍ Scribed by Jiping Liu; Huishan Zhou

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
218 KB
Volume
170
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

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.

πŸ“œ 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
Induced matchings in cubic graphs
Induced matchings in cubic graphs
✍ Peter HorΓ‘k; He Qing; William T. Trotter πŸ“‚ Article πŸ“… 1993 πŸ› John Wiley and Sons 🌐 English βš– 527 KB

## Abstract In this paper, we show that the edge set of a cubic graph can always be partitioned into 10 subsets, each of which induces a matching in the graph. This result is a special case of a general conjecture made by ErdΓΆs and NeΕ‘etΕ™il: For each __d__ β‰₯ 3, the edge set of a graph of maximum de

Maximum matchings in sparse random graph
Maximum matchings in sparse random graphs: Karp–Sipser revisited
✍ Jonathan Aronson; Alan Frieze; Boris G. Pittel πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 490 KB πŸ‘ 1 views

We study the average performance of a simple greedy algorithm for finding a matching in a sparse random graph G , where c ) 0 is constant. The algorithm was first n, c r n w proposed by Karp and Sipser Proceedings of the Twenty-Second Annual IEEE Symposium on x Foundations of Computing, 1981, pp. 3