Seminar of Graph Theory - Robert Lukoťka (1.12.2016)
Thursday 1.12.2016 at 9:50, Lecture room M/213
Robert Lukoťka:
Short cycle covers of graphs
Abstract:
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.