Cop, Robber, and Alarms

Cop, Robber, and Alarms is a game played with one cop and partial information about the location of the robber. In this game, the cop receives partial information from "alarms", which are placed on some of the vertices of the graph. When the robber lands on a vertex with an alarm, the cop learns of the robber’s position. However, the cop does not know which direction the robber goes after leaving an alarmed vertex. We will try to find and characterize the minimum number of alarms required, denoted A(G), to guarantee the capture of the robber on a copwin graph G.

First, we will look at one scheme for placing alarms on vertices of a specific kind of tree: a k-ary tree.

What is a k-ary tree? Read on!

Definitions

The neighborhood of a vertex v in a graph G, denoted N(v), is the set of vertices adjacent to v.

                Example (below): the neighborhood of vertex a, N(a) = {r, b, e}.

A rooted tree is a tree with one vertex r chosen as root.

                The graph below is a rooted tree with vertex r chosen as the root.

For each vertex v, let P(v) be the unique v, r-path.

                Example: P(c) = c, b, a, r

The parent of v is its neighbor on P(v).

                Example: the parent of c is b.

The children of v are its other neighbors.

                Example: c does not have any children because it is a leaf, but the children of b are c and d.  

A full complete k-ary tree is a tree where all vertices except the leaves have exactly k children, and the distance between the root and all leaves is the same.

The graph below is a full complete k-ary tree where k = 2. The distance between the root and each leaf is 3. All vertices except the leaves have two children.

The depth of a full tree is defined to be the distance between the root and all leaves.

                Example: The depth of the tree below is 3.

Alarms on k-ary Trees

Suppose we are given a full complete k-ary tree T. We already know that all trees are copwin. So, here is one scheme for placing alarms on the vertices of a k-ary tree to guaruntee capture of the robber:

·         All leaves remain unalarmed

·         All vertices at distance d ≡ 0 (mod 5) from the leaves receive alarms

·         The vertices in between (vertices at distance d ≡ i (mod 5), i ≠ 1 from the leaves) have exactly one unalarmed child.

By following the scheme laid out above, we can come up with this arrangement of alarms where the alarms are shown as red dots. By following the guidelines above, other alarm arrangements exist but with the same number of alarms. Comment with another arrangement of alarms!

From this, we get the following theorem…

Theorem: Let T be a full complete k-ary tree of depth m. Then...

We can check this theorem for our k-ary tree above by plugging in k = 2, and m = 3. 

We get A(T) ≤ 4

The proof for this can be found here

Several other schemes for copwin graphs have been developed which are different from the scheme for k-ary trees given above.

Alarms on Copwin Graphs

We need some more definitions first…

Copwin Ordering and Copwin Spanning Tree

A finite graph is copwin if and only if it has a copwin ordering. This means that a graph is copwin if and only if it can be reduced to a single vertex, v_n, by successively removing corners.

A graph G is dismantlable if there is an ordering (v₁, v₂, . . . , v_n) of the vertices of G such that for each i < n, v_i is a corner in the subgraph induced by {v_i , v_i+1, . . . , v_n}. Such an ordering of the vertices is called a copwin ordering.

This is confusing in words but makes more sense with a picture...

Jeliazkova, Diana. 2006. Aspects of the cops and robber game played with incomplete information. Acadia University.

The copwin graph above has a copwin ordering (11, 12, 13, 10, 6, 7, 8, 9, 5, 2, 3, 4, 1). This means we begin eliminating corners with any of the vertices 11, 12, 13, or 10. We now consider the graph without those vertices to the right. We can see that 6, 7, 8, and 9 are all corners so we can remove them as well. We move to the right in the diagram where all vertices except 1 are corners. Hence, we are left with a single vertex. 

A spanning tree constructed from a copwin ordering of G keeps track of the removal of corners. A copwin Spanning Tree, S, is constructed as follows:

Let G_i be the induced subgraph of G, such that G_i = G_i−1 − v_i−1, for all i = 2, 3, . . . , n, and G₁ = G. In more simple terms, G_i is the graph G after the successive removal of corners {v₁, v₂, . . . , v_i−1}.

For example, from the graph above, G₁ is the original graph. G₂ = G₁ – 11 and G₃ = G₂ – 12 and so forth where the numbers being subtracted are single vertices.

Let f_i : G_i → G_i+1 be the retraction map from G_i to G_i+1, which maps the corner v_i onto a vertex that dominates v_i in G_i .

Consider a fixed copwin ordering (v₁, v₂, . . . , v_n) of G. The start vertex of the copwin ordering, v_n, will be the root of the spanning tree, and for all vertices v₁, v₂ ∈ V (G), v₁v₂ ∈ E(S) if and only if f_j (v₁) = v₂ or f_j (v₂) = v₁, for some j.

In our example from the copwin graph above, v_n = 1 so 1 will be the root of the spanning tree. Let’s consider the example i = 2. We can see that v₂ = 12 from our copwin ordering. So we know that moving from G₂ to G₃, we took away the vertex labeled 12. So this function tells us to map v₂ = 12 onto a vertex that dominates it in G₂. We can see that vertex 3 dominates vertex 12 in G₂. So, in our copwin spanning tree, there will be an edge between 12 and 3 (below). 

Jeliazkova, Diana. 2006. Aspects of the cops and robber game played with incomplete information. Acadia University.

Now that we have defined a copwin spanning tree, S, let's look at schemes for placing alarms in a copwin graph to guarantee the capture of the robber.

Consider a copwin graph G with a given copwin ordering (x₁, x₂,. . . x_n).

More Definitions!

A vertex x of G is controlled if x remains free, while all neighbors of x are alarmed.

A path P of G is a freepath if all vertices of P are free.

A path P = x_i1 , x_i2 , . . . , x_im of G, where m ≥ 2, is said to be collapsible if P is a path in S_xn and, if x_n ∈ V (P), then x_n is an endpoint of P.

A freepath P’ of G is isolated if all vertices of P’ are at distance at least three from any unalarmed vertex not in P’.

A collapsible freepath P’’ with vertices x_i1 , x_i2 , . . . , x_im is almost isolated if P’’ is isolated in G − L(x_i2 ), where L(x_i2) is the set of leaves adjacent to x_i2.

Assuming P’’ is an induced subgraph of G, the subgraph induced by V (P’’) ∪ L(x_i2 ) is referred to as a free area.

Placing the Minimum Number of Alarms on a Copwin Graph

For a fixed copwin ordering (x₁, x₂, . . . , x_n) of G, define ℵ(S_xn) as the minimum number of vertices with alarms, such that:

1. Free vertices are either controlled or form collapsible freepaths (or free areas)
2. Freepaths are induced subgraphs of G
3. Freepaths are either isolated or almost isolated, and
4. If an alarmed vertex x_i has more than one unalarmed neighbor, then one of the following occcurs:

(a) x_i is adjacent to a finite number of unalarmed leaves,

(b) x_i lies on a collapsible path with exactly two controlled vertices,

(c) The unalarmed neighbors of x_i lie on the same freepath P = x_i1 , x_i2 , . . . , x_im, and i > i_m

(d) x_i has exactly two unalarmed neighbors that lie on the same freepath P.

Define ℵ_G = min_Sv {ℵ(S_v)|S_v is a copwin spanning tree of G}.

Theorem: Let G be a finite copwin graph. Then A(G) ≤ ℵ_G.

This is a bit confusing because you have to look at both the original graph, G, and the copwin spanning tree, S, when placing the alarms. Overall, you want to configure the alarms such that the cop searches free areas and free paths until an alarm is triggered. Then the cop knows which free area the robber is leaving and which free area he is entering.

Conclusion

Like other variants of cops and robbers, Cop, Robber, and Alarms seems to be suited more towards playing on a computer. Cop, Robber, and Alarms can also be played with the alarms on the edges instead of on the vertices. Even further, this variant of Cops and Robbers can be played and analyzed with more than one cop. This idea of a game played with one cop and partial information about the location of the robber has many variations with different amounts and timings of the partial information. For example, in a witness version of the Cops and Robber game, cops have partial information provided via witnesses who report “sightings” of the robber. This is similar to the alarms version but sightings occur at regular intervals. Thus, the cop's strategy is different because she can just sit and wait for the witness to tell her the location of the robber. Overall, with the help of many many definitions of relationships between vertices, we can place the minimum number of alarms on a copwin graph to guarantee capture of the robber. 

Works Cited

Clarke, N. E. (2009). A witness version of the Cops and Robber game. Discrete Mathematics, 3292-3298.

Connon, N. E. (2006). Cops, Robber, and Alarms. Ars Combinatoria -Waterloo then Winnipeg.

Jeliazkova, Diana. 2006. Aspects of the cops and robber game played with incomplete information. Acadia University.