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. |