×

Connected graph searching for unicyclic graphs. (English) Zbl 1190.94052

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

Citations:

Zbl 1255.68105
PDFBibTeX XMLCite
Full Text: Link