TY - JOUR

T1 - Contraction obstructions for connected graph searching

AU - Best, Micah J.

AU - Gupta, Arvind

AU - Thilikos, Dimitrios M.

AU - Zoros, Dimitris

N1 - Publisher Copyright:
© 2015 Elsevier B.V.

PY - 2016/8/20

Y1 - 2016/8/20

N2 - We consider the connected variant of the classic mixed search game where, in each search step, cleaned edges form a connected subgraph. We consider graph classes with bounded connected (and monotone) mixed search number and we deal with the question whether the obstruction set, with respect of the contraction partial ordering, for those classes is finite. In general, there is no guarantee that those sets are finite, as graphs are not well quasi ordered under the contraction partial ordering relation. In this paper we provide the obstruction set for k=2, where k is the number of searchers we are allowed to use. This set is finite, it consists of 177 graphs and completely characterises the graphs with connected (and monotone) mixed search number at most 2. Our proof reveals that the “sense of direction” of an optimal search searching is important for connected search which is in contrast to the unconnected original case. We also give a double exponential lower bound on the size of the obstruction set for the classes where this set is finite.

AB - We consider the connected variant of the classic mixed search game where, in each search step, cleaned edges form a connected subgraph. We consider graph classes with bounded connected (and monotone) mixed search number and we deal with the question whether the obstruction set, with respect of the contraction partial ordering, for those classes is finite. In general, there is no guarantee that those sets are finite, as graphs are not well quasi ordered under the contraction partial ordering relation. In this paper we provide the obstruction set for k=2, where k is the number of searchers we are allowed to use. This set is finite, it consists of 177 graphs and completely characterises the graphs with connected (and monotone) mixed search number at most 2. Our proof reveals that the “sense of direction” of an optimal search searching is important for connected search which is in contrast to the unconnected original case. We also give a double exponential lower bound on the size of the obstruction set for the classes where this set is finite.

KW - Graph contractions

KW - Graph searching

KW - Obstruction set

UR - http://www.scopus.com/inward/record.url?scp=84939825757&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84939825757&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2015.07.036

DO - 10.1016/j.dam.2015.07.036

M3 - Article

AN - SCOPUS:84939825757

SN - 0166-218X

VL - 209

SP - 27

EP - 47

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -