Matchings and walks in graphs

✍ Scribed by C. D. Godsil

• Publisher: John Wiley and Sons
• Year: 1981
• Tongue: English
• Weight: 527 KB
• Volume: 5
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.3190050310

✦ Synopsis

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{article}\pagestyle{empty}\begin{document}$ \frac{{\alpha (G\backslash v, x)}}{{\alpha (G, x)}} = \frac{{\alpha (T\backslash w, x)}}{{\alpha (T, x)}}. $\end{document}

This result has a number of consequences. Here we use it to prove that α(G_v_, 1/x)/__x__α(G, 1/x) is the generating function for a certain class of walks in G. As an application of these results we then establish some new properties of α(G, x).