Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, July 05, 2016, 12:15 pm
Duration: 30 minutes
Location: CAB G11
Speaker: Milos Trujic
The celebrated result of Dirac states that any graph on n > 2 vertices with minimum degree at least n/2 contains a Hamilton cycle. Recently, Balogh, Mousset, and Skokan generalised this result by showing that for any integer k > 1 and sufficiently large n, the vertex set of a graph G on n vertices with minimum degree at least n/k can be covered by at most k - 1 cycles.
In this thesis we extend the result of Balogh et al. to a sparse setting. Namely, we show that for any integer k > 1 the vertex set of a random graph G(n, p) with p > n^(-1 + o(1)) can be covered by at most k - 1 cycles even after removing at most ((k - 1)/k - o(1))-fraction of the edges touching each vertex. Our results are optimal with respect to the constant (k - 1)/k and almost optimal with respect to the edge probability p.
Thesis supervised by Angelika Steger, Frank Mousset, and Nemanja Škorić.
Automatic MiSe System Software Version 1.4803M | admin login