No label defined (Q4035355)

[For the entire collection see Zbl 0753.00028.] Graph searches are best described by imagining a finite set of guards chasing a prisoner around a graph. A move consists of placing a guard at a vertex, removing a guard from a vertex, or sliding a guard along an edge. After each move the prisoner is free to move instantaneously along any path in the graph that avoids the guards. The goal is to find an efficient search strategy which eventually captures the prisoner, more specifically, to do so with the fewest number of guards. This mimimum number is called the search number of the graph. In general, finding the search number of a graph is NP-hard. Variations on this basic search game include node-searching and \(t\)-searching. In this paper the author surveys connections between various search games and graph parameters such as interval width, tree-width, and path-width. These parameters measure how closely the graph resembles a tree or path. They play a central role in the recent work on graph minors. The author discusses how ideas from the graph minor research lead to a short proof of monotonicity in mixed searching.