Premium
Extremal Graphs With a Given Number of Perfect Matchings
Author(s) -
Hartke Stephen G.,
Stolee Derrick,
West Douglas B.,
Yancey Matthew
Publication year - 2013
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21687
Subject(s) - mathematics , combinatorics , corollary , conjecture , upper and lower bounds , constant (computer programming) , graph , extremal graph theory , discrete mathematics , strong perfect graph theorem , chordal graph , 1 planar graph , line graph , voltage graph , computer science , mathematical analysis , programming language
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 ) = n 2 / 4 + c pfor some constant c p when n is at least some constant n p . For p ≤ 6 , they also determined c p and n p . 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 c p and n p for p ≤ 10 . We also present lower bounds on f ( n , p ) proving thatc p > 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.