Seminár z teórie grafov - Robert Lukoťka (1.12.2016)

vo štvrtok 1.12.2016 o 9:50 hod. v miestnosti M/213

---

Prednášajúci: Robert Lukoťka 

Názov: Short cycle covers of graphs

Termín: 1.12.2016, 9:50 hod., M/213

Abstrakt:
Let G be a bridgeless graph. A circuit cover \CC of G is a collection of circuits such that each edge of G is contained in some circuit from \CC. The length of \CC is the sum of the lengths of the circuits from \CC. The problem of finding short circuit cover can be reduced to weighted cubic graph (where the weights represent lengths of the edges). We show that a bridgeless cubic unweighted graph G has a circuit cover of total length at most 1.6 |E(G)|. Stronger bounds can be obtained if the structure of 5-circuts in G is restricted or when higher cyclic connectivity is assumed.

---