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$.
$\begingroup$
$\endgroup$
asked Apr 17, 2010 at 2:40
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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.
-
3$\begingroup$ 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/v15i1n13.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. $\endgroup$ Commented Apr 17, 2010 at 21:42
-
$\begingroup$ The link to
sciencedirect.comis broken, but the article can be found at doi:10.1016/j.disc.2009.08.016 (Zbl 1214.05120). $\endgroup$ Commented May 18, 2023 at 5:37 -
$\begingroup$ The link to
emis.ams.orgin a comment above seems to be broken, but the article can be found at the new website of the EMIS, or at EuDML, or at arXiv:0803.2578 [math.CO] (Zbl 1183.05064). $\endgroup$ Commented May 18, 2023 at 5:44