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.