On matchings in graphs (Q2713637)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: On matchings in graphs |
scientific article; zbMATH DE number 1602767
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On matchings in graphs |
scientific article; zbMATH DE number 1602767 |
Statements
10 June 2001
0 references
matching
0 references
0.95510626
0 references
0 references
0.9499784
0 references
0 references
0.9453931
0 references
0.94509655
0 references
0 references
0 references
0 references
On matchings in graphs (English)
0 references
A matching in a graph is a set of pairwise independent edges. The paper surveys the relationship between the maximum size of a matching and the minimum size of an (inclusion-wise) maximal matching in a given graph. It presents bounds, proves their tightness and proves interpolation theorems. The second part of the paper is devoted to the study of the so-called matching graph, i.e., the graph whose vertices are maximum matchings in a given graph, and two maximum matchings are adjacent if they differ in precisely two edges. Some properties of the matching graphs are identified, but the question of characterizing matching graphs is still open.
0 references
