Extremal Graphs With a Given Number of Perfect Matchings. Issue 4 (16th July 2012) - Hartke, Stephen G.
Abstract Let f(n, p) denote the maximum number of edges in a graph having n vertices and exactly p perfect matchings. For fixed p, Dudek and Schmitt showed that f(n, p)=n2/4+cp for some constant cp when n is at least some constant np. For p≤6, they also determined cp and np. For fixed p, we show that the extremal graphs for all n are determined by those with O(p) vertices. As a corollary, a computer search determines cp and np for p≤10. We also present lower bounds on f(n, p) proving that cp>0 for p≥2 (as conjectured by Dudek and Schmitt), and we conjecture an upper bound on f(n, p). Our structural results are based on Lovász's Cathedral Theorem.