Extremal Graphs With a Given Number of Perfect Matchings. Issue 4 (16th July 2012)

• Record Type: Journal Article
• Authors: Hartke, Stephen G.; Stolee, Derrick; West, Douglas B.; Yancey, Matthew
• Is Part Of: Journal of graph theory. Volume 73:Issue 4(2013)
• Page Start: 449
• Page End: 468
• Publication Date: 2012-07-16
• Subjects: Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.21687
• Languages: English
• ISSNs: 0364-9024

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>Let <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg21g21xj1" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21687:jgt21687-math-0001" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>f</mml:mi><mml:mo>(</mml:mo><mml:mi>n</mml:mi><mml:mo>, </mml:mo><mml:mi>p</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:math> denote the maximum number of edges in a graph having <italic>n</italic> vertices and exactly <italic>p</italic> perfect matchings. For fixed <italic>p</italic>, 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" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21687:jgt21687-math-0002" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>f</mml:mi><mml:mrow><mml:mo>(</mml:mo><mml:mi>n</mml:mi><mml:mo>, </mml:mo><mml:mi>p</mml:mi><mml:mo>)</mml:mo></mml:mrow><mml:mo>=</mml:mo><mml:msup><mml:mi>n</mml:mi><mml:mn>2</mml:mn></mml:msup><mml:mo>/</mml:mo><mml:mn>4</mml:mn><mml:mo>+</mml:mo><mml:msub><mml:mi>c</mml:mi><mml:mi>p</mml:mi></mml:msub></mml:mrow></mml:math> for some constant <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg21g21xbq" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21687:jgt21687-math-0003" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi>c</mml:mi><mml:mi>p</mml:mi></mml:msub></mml:math> when <italic>n</italic> 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" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21687:jgt21687-math-0004" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi>n</mml:mi><mml:mi>p</mml:mi></mml:msub></mml:math>. For <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg21g21x8m" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21687:jgt21687-math-0005" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>p</mml:mi><mml:mo>≤</mml:mo><mml:mn>6</mml:mn></mml:mrow></mml:math>, they also determined <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg21g21xgx" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21687:jgt21687-math-0006" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi>c</mml:mi><mml:mi>p</mml:mi></mml:msub></mml:math> and <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg21g21xhg" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21687:jgt21687-math-0007" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi>n</mml:mi><mml:mi>p</mml:mi></mml:msub></mml:math>. For fixed <italic>p</italic>, we show that the extremal graphs for all <italic>n</italic> 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" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21687:jgt21687-math-0008" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>O</mml:mi><mml:mo>(</mml:mo><mml:msqrt><mml:mi>p</mml:mi></mml:msqrt><mml:mo>)</mml:mo></mml:mrow></mml:math> 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" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21687:jgt21687-math-0009" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi>c</mml:mi><mml:mi>p</mml:mi></mml:msub></mml:math> and <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg21g21x29" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21687:jgt21687-math-0010" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi>n</mml:mi><mml:mi>p</mml:mi></mml:msub></mml:math> for <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg21g21x4d" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21687:jgt21687-math-0011" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>p</mml:mi><mml:mo>≤</mml:mo><mml:mn>10</mml:mn></mml:mrow></mml:math>. 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" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21687:jgt21687-math-0012" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>f</mml:mi><mml:mo>(</mml:mo><mml:mi>n</mml:mi><mml:mo>, </mml:mo><mml:mi>p</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:math> proving that <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg21g21wxk" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21687:jgt21687-math-0013" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi>c</mml:mi><mml:mi>p</mml:mi></mml:msub><mml:mo>></mml:mo><mml:mn>0</mml:mn></mml:mrow></mml:math> for <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg21g21wz4" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21687:jgt21687-math-0014" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>p</mml:mi><mml:mo>≥</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:math> (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" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21687:jgt21687-math-0015" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>f</mml:mi><mml:mo>(</mml:mo><mml:mi>n</mml:mi><mml:mo>, </mml:mo><mml:mi>p</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:math>. Our structural results are based on Lovász's Cathedral Theorem.</p> </abstract>