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