Graphs with monotone connected mixed search number of at most two

Graph searching is used to model a variety of problems and has close connections to variations of path-decomposition. This work explores Monotone Connected Mixed Search. Metaphorically, we consider this problem in terms of searchers exploring a network of tunnels and rooms to locate an opponent. In one turn this opponent moves arbitrarily fast while the searchers may only move to adjacent rooms. The objective is, given an arbitrary graph, to determine the minimum number of searchers for which there exist a valid series of moves that searches the graph. We show that the family of graphs requiring at most k searchers is closed under graph contraction. We exploit the close ties between the contraction ordering and the minor ordering to produce a number of structural decomposition techniques and show that there are 172 obstructions in the contraction order for the set of graphs requiring at most two searchers.