✦ LIBER ✦

Counting Matchings in Graphs

✍ Scribed by E.J. Farrell

Publisher: Elsevier Science
Year: 1987
Tongue: English
Weight: 488 KB
Volume: 324
Category: Article
ISSN: 0016-0032
DOI: 10.1016/0016-0032(87)90046-9

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

Matchings in polytopal graphs

✍ B. Grünbaum 📂 Article 📅 1974 🏛 John Wiley and Sons 🌐 English ⚖ 667 KB

Counting perfect matchings in hexagonal

Counting perfect matchings in hexagonal chains

✍ Peter E. John 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 265 KB

Induced matchings in bipartite graphs

✍ R.J. Faudree; A. Gyárfas; R.H. Schelp; Zs. Tuza 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 454 KB

Matchings and walks in graphs

✍ C. D. Godsil 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 527 KB

## Abstract The matching polynomial α(__G, x__) of a graph __G__ is a form of the generating function for the number of sets of __k__ independent edges of __G__. in this paper we show that if __G__ is a graph with vertex __v__ then there is a tree __T__ with vertex __w__ such that \documentclass{ar

Induced matchings in cubic graphs

✍ Peter Horák; He Qing; William T. Trotter 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 527 KB

## Abstract In this paper, we show that the edge set of a cubic graph can always be partitioned into 10 subsets, each of which induces a matching in the graph. This result is a special case of a general conjecture made by Erdös and Nešetřil: For each __d__ ≥ 3, the edge set of a graph of maximum de

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