Game Development Reference
In-Depth Information
B n consisting of all crosses
{
( s, j ):1
j<n
}∪{
( i, t ):1
i<n
}
, where
1
s, t < n , of the sub-grid induced by the vertices
{
( i, j ):1
i, j
n
1
}
together with the sets B :=
}
containing the bottom-most row and the right-most column except the last
vertex of that column.
It is readily verified that this is a bramble. Clearly any pair of crosses
shares a vertex and therefore touches. On the other hand, every cross touches
the bottom row B and also the rightmost column R . Finally, B and L touch
also.
The order of
{
( n, j ):1
j
n
}
and R :=
{
( i, n ):1
i<n
n we need two
vertices to cover B and R , and they are disjoint and also disjoint from the
other elements in
B
n is n + 1. For, to cover every element of
B
1 vertices
as otherwise there would be a row and a column in the sub-grid of G n without
the bottom-row and right-most column from which no vertex would have
been chosen. But then the corresponding cross would not be covered.
Grids therefore provide examples of graphs with very high bramble width.
We will show now that this also implies that the number of cops needed
to search the graph is very high. The following is the easy direction of the
theorem below.
B
n . But to cover the crosses we need at least n
Lemma 7.33
is a bramble of order k +1 in a graph G then the robber
wins against k cops on G.
If
B
Proof We describe a winning strategy for the robber against k cops. Let
X be the initial position of the cops. As the order of
B
is k + 1, there is at
least one set B
not containing any cops and the robber can choose any
vertex from this set. Now, suppose that after some steps, the cops are on X
and the robber is on a vertex in a set B
∈B
not containing any cop. Now
suppose the cops go from X to X .If X does not contain a vertex from B
then the robber does not move. Otherwise, there is a B ∈B
∈B
not containing
any vertex from X and while the cops move from X to X , the robber can
go from his current position in B to a new position in B as B and B are
connected and touch. This defines a winning strategy for the robber.
The converse of the previous result is also true but much more complicated
to show.
Theorem 7.34 (Seymour and Thomas [1993])
Let G be a graph and k
0
be an integer. G contains a bramble of order
k if, and only if, no fewer
than k cops have a winning strategy in the visible Cops and Robber game on
G if, and only if, no fewer than k cops have a monotone winning strategy in
the visible Cops and Robber game on G.