| Abstract: | The matching graph M(G) of a graph G is that graph whose vertices are the maximum matchings in G and where two vertices M1 and M2 of M(G) are adjacent if and only if |M1 − M2| = 1. When M(G) is connected, this graph models a metric space whose metric is defined on the set of maximum matchings in G. Which graphs are matching graphs of some graph is not known in general. We determine several forbidden induced subgraphs of matching graphs and add even cycles to the list of known matching graphs. In another direction, we study the behavior of sequences of iterated matching graphs. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 73–86, 1998 |
