Searching and pebbling

AbstractWe relate the search number of an undirected graph G with the minimum and maximum of the progressive pebble demands of the directed acyclic graphs obtained by orienting G. Towards this end, we introduce node-searching, a slight variant of searching, in which an edge is cleared by placing searchers on both of its endpoints. We also show that the minimum number of searchers necessary to node-search a graph equals its vertex separator plus one