Computer Science – Discrete Mathematics
Scientific paper
2012-02-14
Computer Science
Discrete Mathematics
Scientific paper
We study a game played on a graph $G$ by a team of $r$ {\it revolutionaries} and a team of $s$ {\it spies}. Initially, revolutionaries and then spies take positions at vertices. In each subsequent round, each revolutionary may move to an adjacent vertex or not move, and then each spy has the same option. The revolutionaries win by holding a meeting of $m$ revolutionaries at some vertex having no spy at the end of a round; the spies win if they can prevent this forever. Let $\sigma(G,m,r)$ denote the minimum number of spies needed to win. Trivially, $\min\{\floor{r/m},|V(G)|\}\le \sigma(G,m,r)\le r-m+1$. We prove that $\sigma(G,m,r)$ equals the lower bound whenever $G$ has a rooted spanning tree $T$ such that every edge of $G$ not in $T$ joins two vertices having the same parent in $T$. Such graphs include graphs that have a dominating vertex. In general, $\sigma(G,m,r)\le\gamma(G)\floor{r/m}$, where $\gamma(G)$ is the domination number, and this bound is nearly sharp when $\gamma(G)\le m$. For fixed $r$ and $m$, there are chordal graphs and bipartite graphs such that $\sigma(G,m,r)=r-m+1$, and this holds also for the random graph. Also $\sigma(G,m,r)=r-m+1$ for hypercubes of dimension at least $r$ when $m=2$. For $r\ge m\ge 3$, the number of spies needed to win on a hypercube of dimension at least $r$ exceeds $r-\frac34 m^2$. For complete $k$-partite graphs with partite sets of size at least $2r$, the leading term in the threshold for spies to win is approximately $\frac k{k-1}\frac rm$ when $k\ge m$. If $G$ is a complete bipartite graph with such large partite sets, then $\sigma(G,2,r)\lceil{\frac{\floor{7r/2}-3}5}\rceil$ and $\sigma(G,3,r)}=\floor{r/2}$. For larger $m$, the threshold is between $\frac{3r}{2m}-3$ and $\frac{(1+1/\sqrt3)r}{m}$.
Butterfield Jane V.
Cranston Daniel W.
Puleo Gregory J.
West Douglas B.
Zamani Reza
No associations
LandOfFree
Revolutionaries and spies: Spy-good and spy-bad graphs 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: Spy-good and spy-bad graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Revolutionaries and spies: Spy-good and spy-bad graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-88518