Lower Bounds and Algorithms for Searching Networks

Abstract

Research on graph searching has recently gained interest in computer science, mathematics, and physics. This thesis provides new results on two graph search models, namely fast searching and the zero-visibility cops and robber model. Given a graph that contains an invisible fugitive, the fast searching problem is to find the fast search number, i.e., the minimum number of searchers to capture the fugitive in the fast search model. This model was first introduced by Dyer, Yang and Ya¸sar in 2008. Although the literature provides a number of results on fast searching, many properties of the fast search number have not yet been revealed. In this thesis, we give new lower bounds on the fast search number. Using the new lower bounds, we prove an explicit formula for the fast search number of the cartesian product of an Eulerian graph and a path. We also give formulas for the fast search number of variants of the cartesian product. We present an upper bound on the fast search number of hypercubes, and extend the results to a broader class of graphs including toroidal grids. In addition, we examine the complete k-partite graphs and provide lower bounds and upper bounds on their fast search number. We also investigate some special classes of complete k-partite graphs, such as complete bipartite graphs and complete split graphs. We solve the open problem of determining the fast search number of complete bipartite graphs, and present upper and lower bounds on the fast search number of complete split graphs. We also introduce the notion of k-combinable graphs, and propose an efficient method for computing the fast search number of such graphs. The zero-visibility cops and robber game is a variant of Cops and Robbers subject to the constraint that the cops have no information at any time about the location of the robber. We first study a partition problem in which for a given graph and an integer k, we want to find a partition of the vertex set such that the size of the boundary of the smaller subset in the partition is at most k while the size of this subset is as large as possible under some conditions. Then we apply such partitions to prove lower bounds on the zero-visibility cop number of graph products. We also investigate the monotonic zero-visibility cop number of graph products. In addition, we prove lower bounds on the zerovisibility cop number for various classes of graphs. In particular, we give lower bounds on the zero-visibility cop number for graph joins and lexicographic products of graphs.