Alspach, Brian; Hanson, Denis; Li, Xiangwen Connected graph searching for unicyclic graphs. (English) Zbl 1190.94052 Adv. Appl. Discrete Math. 5, No. 1, 37-50 (2010). Summary: 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 \(s(G)\) 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 \(cs(G)\) 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. L. Barriére et al. [in: Graph-theoretic concepts in computer science. 29th international workshop, WG 2003, Elspeet, The Netherlands, June 19–21, 2003. Revised papers. Berlin: Springer. Lect. Notes Comput. Sci. 2880, 34–45 (2003; Zbl 1255.68105)] posed an open problem: there exists a constant \(\ell \) such that \(cd(G) \leq \ell s(G)\) for a graph \(G\). In this paper, we prove that \(cs(G) < 2s(G)\) for any unicyclic graph, which extends Barriére et al.’s [loc. cit.] result. Next, one naturally asks how to characterize \(s(G) = cs(G)\) 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. MSC: 94C15 Applications of graph theory to circuits and networks 05C83 Graph minors Keywords:graph searching; graph minor; search number Citations:Zbl 1255.68105 PDFBibTeX XMLCite \textit{B. Alspach} et al., Adv. Appl. Discrete Math. 5, No. 1, 37--50 (2010; Zbl 1190.94052) Full Text: Link