Extended exclusive graph search

Graph search is an important research area in both mathematics and computer science with many practical applications such as eliminating a malicious software in a computer network. The graph search problem can be intuitively described as follows: given a set of searchers and a fugitive in a graph, the searchers and fugitive move from vertices to vertices in the graph alternatively and the searchers try to capture the fugitive which tries to escape from the searchers. A major optimization problem in graph search is to find the minimum number of searchers (called search number) to capture the fugitive. There are several well known graph models: node-search, edgesearch, mixed-search and exclusive search. In this thesis, we propose a new search model which is an extension of the exclusive search. We prove the extended exclusive search number for trees. We give the search numbers for the well known graph search models and the extended exclusive search on trees of rings. We also propose heuristic search algorithms for power law graphs based on these models.