Exponentially many perfect matchings in cubic graphs

ESPERET, L; F KARDOS; King AD; Daniel KRÁĽ a S NORINE. Exponentially many perfect matchings in cubic graphs. Advances in Mathematics. SAN DIEGO: ACADEMIC PRESS INC ELSEVIER SCIENCE, 2011, roč. 227, č. 4, s. 1646-1664. ISSN 0001-8708. Dostupné z: https://doi.org/10.1016/j.aim.2011.03.015.

Základní údaje

Originální název

Exponentially many perfect matchings in cubic graphs

Autoři

ESPERET, L; F KARDOS; King AD; Daniel KRÁĽ a S NORINE

Vydání

Advances in Mathematics, SAN DIEGO, ACADEMIC PRESS INC ELSEVIER SCIENCE, 2011, 0001-8708

---

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Utajení

není předmětem státního či obchodního tajemství

Impakt faktor

Impact factor: 1.177

DOI

https://doi.org/10.1016/j.aim.2011.03.015

UT WoS

000291174600011

Klíčová slova anglicky

Perfect matching; Perfect matching polytope; Cubic graph; Lovasz-Plummer conjecture

---

Anotace

V originále

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.