A structure theorem for maximum internal matchings in graphs (Q1183490): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 00:37, 5 March 2024
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