Searching and pebbling (Q1821562): Difference between revisions

For a directed acyclic graph (dag) D the progressive pebble demand number pb(D) is the minimal number of pebbles needed to place a pebble on every vertex of D exactly once, by using the rules: (i) a pebble can be placed on a vertex if all its predecessors are pebbled; (ii) a pebble can be deleted at any time. For an undirected graph \(G=(V,E)\) the progressive node search number pns(G) is the minimal number of pebbles (called guards) needed to clear all edges of G, by using the rules: (i) a guard can be placed on a vertex at any time; (ii) a guard can be deleted at any time; (iii) an edge becomes clear when both its endpoints contain a guard. The node-search number is defined analogously using the additional rule: (iv) a clear edge becomes contaminated (not clear), when there is a path leading from it to a contaminated edge. The vertex separator of G is \(vs(G)=\min_{L} \max_{i}| \{v\in V|\) L(v)\(\leq i\) and \(\exists w\in V:\) \(L(w)>i\) and \(\{\) v,w\(\}\) is an edge\(\}|\) over all bijective vertex numberings (layouts) L:V\(\to \{1,...,| V| \}.\) The following results are proved: a) \(ns(G)=pns(G)\); b) the problem ''ns(G)\(\leq k?''\) is NP-complete; c) \(ns(G)=\min \{pb(D)|\) D is dag and G is the underlying undirected graph of \(D\}\) ; d) \(ns(G)=vs(G)+1\).