Publication details
Exponentially many perfect matchings in cubic graphs
| Authors | |
|---|---|
| Year of publication | 2011 |
| Type | Article in Periodical |
| Magazine / Source | Advances in Mathematics |
| Citation | |
| Doi | http://dx.doi.org/10.1016/j.aim.2011.03.015 |
| Keywords | Perfect matching; Perfect matching polytope; Cubic graph; Lovasz-Plummer conjecture |
| Description | We show that every cubic bridgeless graph G has at least 2(vertical bar V(G)vertical bar/3656) perfect matchings. This confirms an old conjecture of Lovasz and Plummer. (C) 2011 Elsevier Inc. All rights reserved. |