Large Graphs with p perfect matchings (2010)

Originators: John Schmitt and Andrzej Dudek    (presented by D. West - REGS 2010)

Definitions: Let f(n,p) be the maximum number of edges in an n-vertex graph having exactly p perfect matchings.

Background: Long ago, Hetyei proved that f(n,1)=n²/4 (see Lovász [L]). The construction for the lower bound is a special case of a recursive construction that yields lower bounds for all p. Let G be an n-vertex graph with p perfect matchings. Form G' from G by adding an isolated vertex and then adding a vertex adjacent to all n+1 vertices now present. Note that G' has n+2 vertices and exactly p perfect matchings. Thus f(n+2,p)≥f(n,p)+(n+1). Starting with K₂ yields f(n,1)≥n²/4. To prove equality, take the one perfect matching in G and observe that the four vertices in any two of these edges induce at most two additional edges; summing these bounds yields |E(G)|≤n²/4.

The extremal graph for f(n,1) is unique, as is the extremal graph for f(n,2). In general, the graph obtained from Hetyei's graph on n-2s vertices by adding s isolated vertices and then s vertices adjacent to all others has s! perfect matchings and n²/4+(s²-s)/2 edges.

Conjecture 1: (West) f(n,s!)=n²/4+(s²-s)/2 when n≥2s, achieved uniquely by the graph constructed above.

Conjecture 2: (Dudek-Schmitt) f(n,∏_1≤i≤t(2i-1))=n²/4+(t²-t) when n≥2t, achieved by starting with K_2t and applying the recursive construction, adding two vertices at each step.

Question 3: (Dudek-Schmitt) When does equality hold in the recursive lower bound f(n+2,p)≥f(n,p)+(n+1)?

Conjecture 4: For every fixed p, the value of f(n,p) has the form n²/4+c_p for some fixed integer c_p whenever n is large enough to permit a graph with exactly p perfect matchings.

Comments: If the answer to Question 3 is "always" when n is large enough to permit a graph with p perfect matchings, then Conjectures 2 and 4 follow. Dudek and Schmitt determined f(n,p) for p≤6, and it has the form specified in Conjecture 4, with c_p equal to 0, 1, 2, 2, 2, 3 as p runs from 1 to 6.

The general bounds in [DS] are n²/4-(p-2)(p-1)≤f(n,p)≤n²/4+(p-1) for p≥4 and n≥2p, but it seems clear that the lower bound should exceed n²/4.

References:
A. Dudek and J. Schmitt, On the size and structure of graphs with a constant number of 1-factors (June 10, 2010), pdf.
L. Lovász, Combinatorial Problems and Exercises (North-Holland, 1979).