In this seminar, themes stemming from Graph Theory are presented in 1:30h talks (in either english or german).

The seminar is aimed to both bachelor and master students. No written work is required.

Place and Time: t.b.a. If you are interested, send an email to Dr. Lucia Penso.

The themes may be picked either from a book (for instance, Game of Cops and Robbers, from the library), an online survey, an online article, or a mix. We will give priority to themes which involve a sort of game in the graph through movement (such as with walks or propagations).  Results can be either structural or algorithmical. Possible themes:

  • Cop Number (the minimum number of cops able to catch a robber in different graphs (outerplanar, planar,  infinite, random, etc...) and its variations - see "Game of Cops and Robbers from Bonato and Nowakowski"
  • Brush Number (how brushes should be distributed to clean a graph) - see a description in same book
  • Firefighting Number (how firefighters should be placed in a graph to avoid in the best of ways the spreading of fire) - see a description in same book
  • Disease Propagation (minimum set of nodes able to spread a disease with a local or global rule, such as a threshold on contaminated neighbors or shortest paths) - see "On the geodetic hull number of P_k-free graphs" by Dourado, Penso and Rautenbach
  • Blackhole Search (a set of agents must walk to find destructive nodes) - see a short online survey in "Identifying Hostile Nodes in Networks Using Mobile Agents" by Markou in Bulletin of EATCS, or in online surveys by Nicola Santoro
  • Rendez-Vous (a set of agents wants to meet, with advice, sense of direction, or not) - see online surveys and articles by Santoro, Flocchini and Fraigniaud