Matchings and walks in graphs
Author:
- 1 September 1981
- journal article
- Published by Wiley in Journal of Graph Theory
- Vol. 5 (3) , 285-297
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}$ \frac{{\alpha (G\backslash v, x)}}{{\alpha (G, x)}} = \frac{{\alpha (T\backslash w, x)}}{{\alpha (T, x)}}. $ 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).Keywords
This publication has 5 references indexed in Scilit:
- Spectral conditions for the reconstructibility of a graphJournal of Combinatorial Theory, Series B, 1981
- On the calculation of the acyclic polynomialTheoretical Chemistry Accounts, 1978
- Algebraic Graph Theory1974
- Theory of monomer-dimer systemsCommunications in Mathematical Physics, 1972
- A congruence theorem for treesPacific Journal of Mathematics, 1957