A structure theorem for maximum internal matchings in graphs (Q1183490)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A structure theorem for maximum internal matchings in graphs |
scientific article |
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
