Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, February 19, 2015, 12:15 pm
Duration: 30 minutes
Location: CAB G51
Speaker: Jozef Skokan (London School of Economics)
A classical result in graph theory, Dirac's Theorem, states that any graph on n>2 vertices with minimum degree at least n/2 contains a cycle through all of its vertices. One of possible generalizations is to decrease the minimum degree of the graph and ask how many cycles are needed to cover its vertices. We answer this question and prove the following: For a fixed integer k>1 and n sufficiently large, if G is an n-vertex graph with minimum degree at least n/k, then there are k - 1 cycles in G covering its vertex set. This bound is best possible, as there are graphs with minimum degree n/k-1 that do not have this property.
This is joint work with Jozsef Balogh (UIUC) and Frank Mousset (ETH).
Automatic MiSe System Software Version 1.4803M | admin login