J 2012

Maximum edge-cuts in cubic graphs with large girth and in random cubic graphs

KARDOS, F; Daniel KRÁĽ a Volec J

Základní údaje

Originální název

Maximum edge-cuts in cubic graphs with large girth and in random cubic graphs

Autoři

KARDOS, F; Daniel KRÁĽ a Volec J

Vydání

RANDOM STRUCTURES & ALGORITHMS, HOBOKEN, WILEY, 2012, 1042-9832

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

Označené pro přenos do RIV

Ne

DOI

UT WoS

Klíčová slova anglicky

cubic graphs; random graphs; large girth; edge-cut
Změněno: 6. 11. 2020 09:02, Mgr. Darina Boukalová

Anotace

V originále

We show that for every cubic graph Gwith sufficiently large girth there exists a probability distribution on edge-cuts in Gsuch that each edge is in a randomly chosen cut with probability at least 0.88672. This implies that Gcontains an edge-cut of size at least 1.33008n, where nis the number of vertices of G, and has fractional cut covering number at most 1.127752. The lower bound on the size of maximum edge-cut also applies to random cubic graphs. Specifically, a random n-vertex cubic graph a.a.s. contains an edge-cut of size 1.33008n- o(n). (c) 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012