Subgraphs of maximum matching graphs (Q1769200)

From MaRDI portal





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
    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
    0 references
    neigborhood subgraph
    0 references
    common neighbor subgraph
    0 references

    Identifiers