Title of article :
Matchings in regular graphs: minimizing the partition function
Author/Authors :
Borbényi, Márton Eötvös Loránd University - Budapest, Hungary , Csikvari, Peter Eötvös Loránd University - Budapest, Hungary
Abstract :
For a graph G on v(G) vertices let mk(G) denote the number of matchings of size k, and consider the partition function MG(λ)=∑nk=0mk(G)λk. In this paper we show that if G is a d--regular graph and 0<λ<(4d)−2, then
1v(G)lnMG(λ)>1v(Kd+1)lnMKd+1(λ).
The same inequality holds true if d=3 and λ<0.3575. More precise conjectures are also given.
Keywords :
matchings , matching polynomial , regular graphs
Journal title :
Transactions on Combinatorics