Revolutionaries and Spies

Details Revolutionaries and Spies Revolutionaries and Spies

2011-06-20

arxiv.org/abs/1106.3838v1

Mathematics

Combinatorics

Scientific paper

Let $G = (V,E)$ be a graph and let $r,s,k$ be natural numbers. ``Revolutionaries and Spies", $\cG(G,r,s,k)$ , is the following two-player game. The sets of positions for player 1 and player 2 are $V^r$ and $V^s$ respectively. Each coordinate in $p \in V^r$ gives the location of a ``revolutionary" in $G$. Similarly player 2 controls $s$ ``spies". We say $u, u' \in V(G)^n$ are adjacent, $u \sim u'$, if for all $1 \leq i \leq n$, $u_i = u'_i$ or $\{u_i,u'_i\} \in E(G)$. In round $0$ player $1$ picks $p_0 \in V^r$ and then player $2$ picks $q_0 \in V^s$. In each round $i \geq 1$ player $1$ moves to $p_i \sim p_{i-1}$ and then player $2$ moves to $q_i \sim q_{i-1}$. Player 1 wins the game if he can place $k$ revolutionaries on a vertex $v$ in such a way that player 1 cannot place a spy on $v$ in his following move. Player 2 wins the game if he can prevent this outcome. Let $k(G,r,s)$ be the maximum value of $k$ such that player $1$ can win $\cG(G,r,s,k)$. We show that if $G$ is an acyclic graph with at least $s+1$ vertices, then $k(G,r,s)= \floor{\frac{r}{s+1}}$. Let $s(G,r,k)$ be the minimum $s$ such that player $2$ can win $\cG(G,r,s,k)$. We show that $\liminf_{r \to \infty} s(\Z^2,r,2)/r \geq 3/4$. Here moves in $\Z^{2}$ are ``king" moves.

Affiliated with

Also associated with

No associations

Rating

Revolutionaries and Spies does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Revolutionaries and Spies, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Revolutionaries and Spies will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-254819