Informace o publikaci
Exponentially many perfect matchings in cubic graphs
Autoři | |
---|---|
Rok publikování | 2011 |
Druh | Článek v odborném periodiku |
Časopis / Zdroj | Advances in Mathematics |
Citace | |
Doi | http://dx.doi.org/10.1016/j.aim.2011.03.015 |
Klíčová slova | Perfect matching; Perfect matching polytope; Cubic graph; Lovasz-Plummer conjecture |
Popis | 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. |