Displaying similar documents to “A Note On Analogies Between Characteristic And The Matching Polynomial Of A Graph”

Mean value for the matching and dominating polynomial

Jorge Luis Arocha, Bernardo Llano (2000)

Discussiones Mathematicae Graph Theory

Similarity:

The mean value of the matching polynomial is computed in the family of all labeled graphs with n vertices. We introduce the dominating polynomial of a graph whose coefficients enumerate the dominating sets for a graph and study some properties of the polynomial. The mean value of this polynomial is determined in a certain special family of bipartite digraphs.

Bipartition Polynomials, the Ising Model, and Domination in Graphs

Markus Dod, Tomer Kotek, James Preen, Peter Tittmann (2015)

Discussiones Mathematicae Graph Theory

Similarity:

This paper introduces a trivariate graph polynomial that is a common generalization of the domination polynomial, the Ising polynomial, the matching polynomial, and the cut polynomial of a graph. This new graph polynomial, called the bipartition polynomial, permits a variety of interesting representations, for instance as a sum ranging over all spanning forests. As a consequence, the bipartition polynomial is a powerful tool for proving properties of other graph polynomials and graph...