Mathematics – Combinatorics
Scientific paper
2009-08-26
Mathematics
Combinatorics
To appear in Combinatorics, Probability & Computing. Revised from the first version, 28 pages
Scientific paper
We introduce two graph polynomials and discuss their properties. One is a polynomial of two variables whose investigation is motivated by the performance analysis of the Bethe approximation of the Ising partition function. The other is a polynomial of one variable that is obtained by the specialization of the first one. It is shown that these polynomials satisfy deletion-contraction relations and are new examples of the V-function, which was introduced by Tutte (1947, Proc. Cambridge Philos. Soc. 43, 26-40). For these polynomials, we discuss the interpretations of special values and then obtain the bound on the number of sub-coregraphs, i.e., spanning subgraphs with no vertices of degree one. It is proved that the polynomial of one variable is equal to the monomer-dimer partition function with weights parameterized by that variable. The properties of the coefficients and the possible region of zeros are also discussed for this polynomial.
Fukumizu Kenji
Watanabe Yusuke
No associations
LandOfFree
New graph polynomials from the Bethe approximation of the Ising partition function does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with New graph polynomials from the Bethe approximation of the Ising partition function, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and New graph polynomials from the Bethe approximation of the Ising partition function will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-625488