✦ LIBER ✦

Matching graphs

✍ Scribed by Eroh, Linda; Schultz, Michelle

Publisher: John Wiley and Sons
Year: 1998
Tongue: English
Weight: 336 KB
Volume: 29
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199810)29:2<73::aid-jgt3>3.0.co;2-9

No coin nor oath required. For personal study only.

✦ Synopsis

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)

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.

📜 SIMILAR VOLUMES

Induced matching extendable graphs

✍ Jinjiang, Yuan 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 261 KB

We say that a simple graph G is induced matching extendable, shortly IM-extendable, if every induced matching of G is included in a perfect matching of G. The main results of this paper are as follows: (1) For every connected IM-extendable graph 2 |V (G)| -2; the equality holds if and only if G ∼

Matching cutsets in graphs

✍ Augustine M. Moshi 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 504 KB

Let G = ( Y E ) be an undirected graph. A subset F of E is a matching cutset of G if no two edges of Fare incident with the same point, and G-F has more components than G. ChGatal [2] proved that it is NP-complete to recognize graphs with a matching cutset even if the input is restricted to graphs w

Matching and symmetry of graphs

✍ Haruo Hosoya 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 809 KB

Collapsible graphs and matchings

✍ Zhi-Hong Chen; Hong-Jian Lai 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 286 KB

## Abstract A graph __G__ is __collapsible__ if for every even subset __R__ ⊆ __V__(__G__), there is a spanning connected subgraph of __G__ whose set of odd degree vertices is __R__. A graph is __reduced__ if it does not have nontrivial collapsible subgraphs. Collapsible and reduced graphs are defi

Counting Matchings in Graphs

✍ E.J. Farrell 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 488 KB

A general formula is derivedfor the matching polynomial of an arbitrary graph G. This yields a methodfor counting matchings in graphs. From the general formula, explicit formulae are deducedfor the number of k-matchings in several well-known families of graphs.

Disjoint matchings of graphs

✍ Kenneth Lebensold 📂 Article 📅 1977 🏛 Elsevier Science 🌐 English ⚖ 250 KB