Informace o publikaci
A NEW LOWER BOUND ON THE NUMBER OF PERFECT MATCHINGS IN CUBIC GRAPHS
| Autoři | |
|---|---|
| Rok publikování | 2009 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | SIAM Journal on Discrete Mathematics |
| Citace | |
| Doi | http://dx.doi.org/10.1137/080723843 |
| Klíčová slova | perfect matching; cubic graph; brick and brace decomposition; perfect matching polytope |
| Popis | 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. |