Revolutionaries and spies on trees and unicyclic graphs

Details Revolutionaries and spies on trees and unicyclic graphs Revolutionaries and spies on trees and unicyclic graphs

2011-10-11

arxiv.org/abs/1110.2274v1

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}

Affiliated with

Also associated with

No associations

Rating

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.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-471589