Subgraphs of maximum matching graphs (Q1769200)

From MaRDI portal





scientific article; zbMATH DE number 2147386
Language Label Description Also known as
default for all languages
No label defined
    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