Confining the Robber on Cographs
share
In this paper, the notions of trapping and confining the robber on a graph are introduced. We present some structural necessary conditions for graphs G not containing the path on k vertices (referred to as P_k-free graphs) for some k≥ 4, so that k-3 cops do not have a strategy to capture or confine the robber on G. Utilizing such conditions, we show that for planar cographs and planar P_5-free graphs the confining cop number is at most one and two, respectively. It is also shown that the number of vertices of a connected cograph on which one cop does not have a strategy to confine the robber has a tight lower-bound of eight. We also explore the effects of twin operations – which are well known to provide a characterization of cographs – on the number of cops required to capture or confine the robber on cographs. We conclude by posing two conjectures concerning the confining cop number of P_5-free graphs and the smallest planar graph of confining cop number of three.
READ FULL TEXT