An improved linear bound on the number of perfect matchings in cubic graphs

ESPERET, L; Daniel KRÁĽ; P SKODA a R SKREKOVSKI. An improved linear bound on the number of perfect matchings in cubic graphs. European Journal of Combinatorics. LONDON: ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD, 2010, roč. 31, č. 5, s. 1316-1334. ISSN 0195-6698. Dostupné z: https://doi.org/10.1016/j.ejc.2009.11.008.

Základní údaje

Originální název

An improved linear bound on the number of perfect matchings in cubic graphs

Autoři

ESPERET, L; Daniel KRÁĽ; P SKODA a R SKREKOVSKI

Vydání

European Journal of Combinatorics, LONDON, ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD, 2010, 0195-6698

---

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: 0.716

DOI

https://doi.org/10.1016/j.ejc.2009.11.008

UT WoS

000278729800011

---

Anotace

V originále

We show that every cubic bridgeless graph with n vertices has at least 3n/4-10 perfect matchings. This is the first bound that differs by more than a constant from the maximal dimension of the perfect matching polytope. (C) 2009 Elsevier Ltd. All rights reserved.