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.

≥

Search Nedrilad ::

Custom Search