Graph searching and interval completion (Q2706178)

In the classical node-search version for a finite simple undirected graph, in a sequence of moves, at every move a searcher is placed at a vertex or is removed from a vertex. Initially all edges are contaminated (uncleared). A contaminated edge \(xy\) is cleared if on \(x\) and \(y\) searchers are placed. A cleared edge \(e\) is recontaminated if there is a path without searchers between \(e\) and a contaminated edge.NEWLINENEWLINENEWLINEThe classical search problem is to find a sequence of moves (a node-search program) such that the maximum number of searchers used at any move is minimal. In this paper, node-search programs with minimal sum of numbers of searchers are studied, where the sum is taken over all moves. This criterion is called search cost.NEWLINENEWLINENEWLINEThe paper shows monotonicity properties (with respect to recontamination) of search programs with smallest cost. The search cost of a graph \(G\) turns out to be the smallest edge number of an interval supergraph of \(G\) as well as the vertex separation sum and the profile of \(G\). Finally, the paper shows how to compute the search cost of the product of graphs and the search cost of a cograph. The corresponding search program can be determined in linear time.