A structure theorem for maximum internal matchings in graphs (Q1183490)
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: A structure theorem for maximum internal matchings in graphs |
scientific article; zbMATH DE number 33329
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A structure theorem for maximum internal matchings in graphs |
scientific article; zbMATH DE number 33329 |
Statements
A structure theorem for maximum internal matchings in graphs (English)
0 references
28 June 1992
0 references
Extended abstract: An external vertex is one of degree one; others are internal vertices. A counterpart of the Gallai-Edmonds structure theorem is proved for matchings that are not required to cover the external vertices of graphs. The appropriate counterpart of Tutte's theorem is derived from this result for the existence of perfect internal matchings in graphs.
0 references
factor-critical graph
0 references
bipartite graph
0 references
Gallai-Edmonds structure theorem
0 references
Tutte's theorem
0 references
perfect internal matchings
0 references
