8

What is the maximal number of perfect matchings a graph $G(V,E)$ can have if $|V|$ and $|E|$ are fixed? I am particularly interested in a case when $|E| = c|V|^2$.

flag

1 Answer

10

I think this is exactly the main result of this recent paper we just published in Discrete Mathematics. Just in case the link doesn't work: this is "Graphs with the maximum or minimum number of 1-factors" by D. Grossa, N. Kahl and J.T. Saccoman. I have read only the abstract. Let me know if this is what you were looking for.

link|flag
1 
 Thank you, this paper really gives the answer. In fact, it seems that the main result was obtained by Alon and Friedland in this paper: emis.ams.org/journals/EJC/Volume_15/PDF/…. There they show that graphs which are union of complete bipartite graphs have the maximum number of perfect matchings among all graphs with the same degree sequence. – Grigory Yaroslavtsev Apr 17 2010 at 21:42

Your Answer

Get an OpenID
or

Not the answer you're looking for? Browse other questions tagged or ask your own question.