Subgraphs of maximum matching graphs (Q1769200)
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: Subgraphs of maximum matching graphs |
scientific article; zbMATH DE number 2147386
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Subgraphs of maximum matching graphs |
scientific article; zbMATH DE number 2147386 |
Statements
Subgraphs of maximum matching graphs (English)
0 references
21 March 2005
0 references
Let \(G\) be a graph. Define \({\mathcal M}(G)\) to be a graph whose vertices are matchings of the maximum size in \(G\) and edges are pairs of matchings that differ on exactly one edge. The author shows that any two nonadjacent vertices in \({\mathcal M}(G)\) may have at most \(2\) common neighbors. If they have exactly \(2\) common neighbors then the neighbors are nonadjacent. Moreover, for any vertex \(M\) in \({\mathcal M}(G)\), each component of the subgraph induced in \({\mathcal M}(G)\) by the set of neighbors of \(M\) is a complete graph.
0 references
neigborhood subgraph
0 references
common neighbor subgraph
0 references