zbMATH — the first resource for mathematics

Interval graphs and searching. (English) Zbl 0566.05056
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.

05C99 Graph theory
68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI
[1] Ellis, J.A.; Sudborough, I.H.; Turner, J.S., Graph separation and search number, (1984), Northwestern Univ. and Washington Univ, Preprint · Zbl 0942.68641
[2] L.M. Kirousis and C.H. Papadimitriou, Searching and pebbling, Theoret. Comput. Sci., Submitted. · Zbl 0616.68064
[3] LaPaugh, A., Technical report, (1983), Princeton Univ
[4] Megiddo, N.; Hakimi, S.L.; Garey, M.R.; Johnson, D.S.; Papadimitriou, C.H., The complexity of searching a graph (preliminary version), Proc. 22nd IEEE found. comp. sci. symp., 376-381, (1981)
[5] Parsons, T.D., Pursuit-evasion in a graph, (), 426-441 · Zbl 0379.05026
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.