Extremal Graphs With a Given Number of Perfect Matchings. Issue 4 (16th July 2012) - Hartke, Stephen G.; Stolee, Derrick; West, Douglas B.; Yancey, Matthew
Abstract Let <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg21g21xj1" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />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 <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg21g21x95" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />f(n, p)=n2/4+cp for some constant <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg21g21xbq" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />cp when n is at least some constant <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg21g21x6h" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />np. For <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg21g21x8m" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />p≤6, they also determined <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg21g21xgx" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />cp and <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg21g21xhg" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />np. For fixed p, we show that the extremal graphs for all n are determined by those with <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg21g21xdt" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />O(p) vertices. As a corollary, a computer search determines <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg21g21xfc" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />cp and <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg21g21x29" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />np for <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg21g21x4d" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />p≤10. We also present lower bounds on <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg21g21x3v" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />f(n, p) proving that <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg21g21wxk" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />cp>0 for <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg21g21wz4" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />p≥2 (as conjectured by Dudek and Schmitt), and we conjecture an upper bound on <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg21g21x06" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />f(n, p). Our structural results are based on Lovász's Cathedral Theorem.