# Mitarbeiterseminar Logik in der Informatik

Freitag, 16. Dezember 2005, 11:15 Uhr

RUD 25, Raum 4.410
## Monotonicity and connectivity for width parameters

Dimitrios M. Thilikos

Universitat Politècnica de Catalunya, Barcelona

The notion of an expansion is a useful framework for defining
several known width parameters on graphs. We survey the
relation of such parameters with search and conquer games.
The goal in these games is to systematically maneuver
searches in order to capture a fugitive who flees around
the graph or alternatively to organize a gradual occupation
of the graph while minimizing specific cost functions.
An important question is the so called "monotonicity
question": does it cost more to search/conquer a graph
if we do not allow the fugitive to visit again "clean"
locations? Another question is the "connectivity question":
does it cost more to search/conquer a graph
if we demand "clean" positions to induce a connected
part of the graph? We use expansions to settle the
monotonicity and the connectivity questions and we
comment related recent results and open problems
on their study.