Abstract: The graph searching
problem was introduced by Parsons. A graph searching consists of a sequence of
operations: place a searcher, move a searcher along an edge and remove a
searcher from a vertex. The purpose of graph searching is to reach a state in
which all the edges are simultaneously clear. The search number of a graph G
is the smallest number of searchers required to clear G.
A search strategy is connected if the set of clear edges always forms a
connected graph. Let denote the minimum number of
searchers required to use a connected search strategy to clear a graph G.
A graph is unicyclic if it contains at most one cycle. Barriére et al. [1]
posed an open problem: there exists a constant such that for a graph G.
In this paper, we prove that for any unicyclic graph, which
extends Barriére et al. [1] result. Next, one naturally asks how to
characterize for a graph G.
In this paper, we investigate trees and unicyclic graphs and prove that for a
tree, there exists one obstruction and for a cyclic graph, there exist four
obstructions.
Keywords and phrases: graph searching, graph minor, search number.
