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

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)leq mis(G)leq cs(G)= ics(G)leq mcs(G)=mics(G).
The first two inequalities can be strict. In the case of trees, we
have mics(G)leq 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.
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)leq mis(G)leq cs(G)= ics(G)leq mcs(G)=mics(G). The first two inequalities can be strict. In the case of trees, we have mics(G)leq 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.

Citation

Barriere, E., Fraigniaud, P., Santoro, N., Thilikos, D. "Connected and internal graph searching". 2002.