SHORT CYCLE COVERS OF GRAPHS WITH MINIMUM DEGREE THREE

KAISER, T Kral; Daniel KRÁĽ; P NEJEDLY a Lidicky B SAMAL R. SHORT CYCLE COVERS OF GRAPHS WITH MINIMUM DEGREE THREE. SIAM Journal on Discrete Mathematics. Philadelphia: SIAM, 2010, roč. 24, č. 1, s. 330-355. ISSN 0895-4801. Dostupné z: https://doi.org/10.1137/080717468.

Základní údaje

Originální název

SHORT CYCLE COVERS OF GRAPHS WITH MINIMUM DEGREE THREE

Autoři

KAISER, T Kral; Daniel KRÁĽ; P NEJEDLY a Lidicky B SAMAL R

Vydání

SIAM Journal on Discrete Mathematics, Philadelphia, SIAM, 2010, 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.626

Označené pro přenos do RIV

Ne

DOI

https://doi.org/10.1137/080717468

UT WoS

000277834800021

Klíčová slova anglicky

cycle cover; cycle double cover; shortest cycle cover

---

Anotace

V originále

The shortest cycle cover conjecture of Alon and Tarsi asserts that the edges of every bridgeless graph with m edges can be covered by cycles of total length at most 7m/5 = 1.400m. We show that every cubic bridgeless graph has a cycle cover of total length at most 34m/21 approximate to 1.619m, and every bridgeless graph with minimum degree three has a cycle cover of total length at most 44m/27 approximate to 1.630m.