ALCOMFT-TR-03-69

Lali Barrière, Pierre Fraigniaud, Nicola Santoro and Dimitrios M. Thilikos
Connected and Internal Graph Searching
Barcelona. Work packages 2 and 4. October 2003.

Abstract: This paper is concerned with the graph searching game. The search number \es(G) of a graph G is the smallest number of searchers required to ``clear'' G. A search strategy is monotone (m) if no recontamination ever occurs. It is connected (c) if the set of clear edges always forms a

connected subgraph. It is internal (i) if the removal of searchers is not allowed. The difficulty of the ``connected'' version and of the ``monotone internal'' version of the graph searching problem comes from the fact that, as shown in the paper, none of these problems is minor closed for arbitrary graphs, as opposed to all known variants of the graph searching problem. Motivated by the fact that connected graph searching, and monotone internal graph searching are both minor closed in trees, we provide a complete characterization of the set of trees that can be cleared by a given number of searchers. In fact, we show that, in trees, there is only one obstruction for monotone internal search, as well as for connected search, and this obstruction is the same for the two problems. This allows us to prove that, for any tree T, \mis(T)=\cs(T). For arbitrary graphs, we prove that there is a unique chain of inequalities linking all the search numbers above. More precisely, for any graph G, \es(G)=\is(G)=\ms(G)<=\mis(G)<=\cs(G)=\ics(G)<=\mcs(G)=\mics(G). The first two inequalities can be strict. In the case of trees, we have \mics(G)<=2 \es(T)-2, that is there are exactly 2 different search numbers in trees, and these search numbers differ by a factor of 2 at most.

Postscript file: ALCOMFT-TR-03-69.ps.gz (201 kb).