Mathematics – Combinatorics
Scientific paper
2011-10-11
Mathematics
Combinatorics
9 pages
Scientific paper
A team of $r$ {\it revolutionaries} and a team of $s$ {\it spies} play a game on a graph $G$. 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 want to hold an {\it unguarded meeting}, meaning $m$ revolutionaries at some vertex having no spy at the end of a round. To prevent this forever, trivially at least $\min\{|V(G)|,\FL{r/m}\}$ spies are needed. When $G$ is a tree, this many spies suffices. When $G$ is a unicyclic graph, $\min\{|V(G)|,\CL{r/m}\}$ spies suffice, and we characterize those unicyclic graphs where $\FL{r/m}+1$ spies are needed. \def\FL#1{\lfloor #1 \rfloor} \def\CL#1{\lceil #1 \rceil}
Cranston Daniel W.
Smyth Clifford D.
West Douglas B.
No associations
LandOfFree
Revolutionaries and spies on trees and unicyclic 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 on trees and unicyclic graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Revolutionaries and spies on trees and unicyclic graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-471589