Interval graphs and searching (Q1059088): Difference between revisions

The interval thickness of a graph G is the minimum clique number of all the interval supergraphs of G. The clique number of a graph is the number of nodes of its biggest complete subgraph. On the other hand, the node- search number is the least number of searchers (pebbles) required to clear the ''contaminated'' edges of a graph. A contaminated edge is cleared by concurrently having two searchers on both of its endpoints. The ''contamination'' may spread from an uncleared edge to a cleared one through an unguarded path. It is proved that for any graph the node- search number is equal to the interval thickness.