Premium
Matching graphs
Author(s) -
Eroh Linda,
Schultz Michelle
Publication year - 1998
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199810)29:2<73::aid-jgt3>3.0.co;2-9
Subject(s) - combinatorics , mathematics , factor critical graph , discrete mathematics , cograph , line graph , chordal graph , matching (statistics) , split graph , indifference graph , graph , pathwidth , graph power , statistics
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, 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