MATCHING GRAPHS

The matching graph M(G) of a graph G is that graph whose vertices are the maximum matchings in G and where two vertices M-1 and M-2 Of M(G) are adjacent if and only if \M-1 - M-2\ = 1 When M(G) is connected, th is graph models a metric space whose metric is defined on the set of m aximum matchings in G. Which graphs are matching graphs of some graph is not known in general. We determine several forbidden induced subgra phs of matching graphs and add even cycles to the list of known matchi ng graphs. In another direction, we study the behavior of sequences of iterated matching graphs. (C) 1998 John Wiley & Sons, Inc. J Graph Th eory 29: 73-86, 1998.