A NEW LOWER BOUND ON THE NUMBER OF PERFECT MATCHINGS IN CUBIC GRAPHS

KRÁĽ, Daniel; JS SERENI a M STIEBITZ. A NEW LOWER BOUND ON THE NUMBER OF PERFECT MATCHINGS IN CUBIC GRAPHS. SIAM Journal on Discrete Mathematics. Philadelphia: SIAM, 2009, roč. 23, č. 3, s. 1465-1483. ISSN 0895-4801. Dostupné z: https://doi.org/10.1137/080723843.

Základní údaje

Originální název

A NEW LOWER BOUND ON THE NUMBER OF PERFECT MATCHINGS IN CUBIC GRAPHS

Autoři

KRÁĽ, Daniel; JS SERENI a M STIEBITZ

Vydání

SIAM Journal on Discrete Mathematics, Philadelphia, SIAM, 2009, 0895-4801

---

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

DOI

https://doi.org/10.1137/080723843

UT WoS

000270193600025

Klíčová slova anglicky

perfect matching; cubic graph; brick and brace decomposition; perfect matching polytope

---

Anotace

V originále

We prove that every n-vertex cubic bridgeless graph has at least n/2 perfect matchings and give a list of all 17 such graphs that have less than n/2 + 2 perfect matchings.