Publication details
A NEW LOWER BOUND ON THE NUMBER OF PERFECT MATCHINGS IN CUBIC GRAPHS
Authors | |
---|---|
Year of publication | 2009 |
Type | Article in Periodical |
Magazine / Source | SIAM Journal on Discrete Mathematics |
Citation | |
Doi | http://dx.doi.org/10.1137/080723843 |
Keywords | perfect matching; cubic graph; brick and brace decomposition; perfect matching polytope |
Description | We prove that every n-vertex cubic bridgeless graph has at least n/2 perfect matchings and give a list of all 17 such graphs that have less than n/2 + 2 perfect matchings. |