## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Thursday, February 19, 2015, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Jozef Skokan (London School of Economics)

## An Extension of Dirac's Theorem

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

Information for students and suggested topics for student talks