W&M Featured Events
This calendar presented by
William & Mary
[PAST EVENT] Mathematics Colloquium/CSUMS Lecture
March 30, 2012
2pm - 3pm
Title: The Game of Revolutionaries and Spies on a Graph
Abstract: We study a pursuit game between two teams on a graph; it can be viewed as modeling a problem of network security. The first team consists of r revolutionaries; the second consists of s spies. The revolutionaries seek a one-time meeting of m revolutionaries free of oversight by spies. Initially, the revolutionaries take positions at vertices, and then the spies do the same. In each subsequent round, each revolutionary may move to an adjacent vertex or not move, and then each spy has the same option. Everyone knows where everyone else is at all times.
The revolutionaries win if after a round there is an unguarded meeting, where a meeting consists of (at least) m revolutionaries on one vertex, and it is unguarded if no spy is there. The spies win if they can prevent this forever. Let RSG denote this game played on the graph G by s spies and r revolutionaries with meeting size m.
The revolutionaries can form [r/m] disjoint meetings (if G has at least this many vertices), so the spies need s greater than [r/m] to avoid losing immediately. For fixed G,r,m, let sigma (G,m,r) be the least s such that RSG is won by the spies. Say that $G$ is spy-good if sigma (G,m,r)=[r/m] for all m and r such that r/m less than |V(G)|. We obtain a large class of spy-good graphs. A webbed tree is a graph G having a rooted spanning tree T such that every edge of G not in T joins vertices having the same parent in T.
Theorem. Every webbed tree is spy-good. Furthermore, all graphs having a dominating vertex are webbed trees.
We also consider the game on hypercubes, unicyclic graphs, large k-partite graphs and graphs with small domination number.
This is joint work with Jane V. Butterfield, Gregory J. Puleo, Clifford D. Smyth, Douglas B. West and Reza Zamani.
Abstract: We study a pursuit game between two teams on a graph; it can be viewed as modeling a problem of network security. The first team consists of r revolutionaries; the second consists of s spies. The revolutionaries seek a one-time meeting of m revolutionaries free of oversight by spies. Initially, the revolutionaries take positions at vertices, and then the spies do the same. In each subsequent round, each revolutionary may move to an adjacent vertex or not move, and then each spy has the same option. Everyone knows where everyone else is at all times.
The revolutionaries win if after a round there is an unguarded meeting, where a meeting consists of (at least) m revolutionaries on one vertex, and it is unguarded if no spy is there. The spies win if they can prevent this forever. Let RSG denote this game played on the graph G by s spies and r revolutionaries with meeting size m.
The revolutionaries can form [r/m] disjoint meetings (if G has at least this many vertices), so the spies need s greater than [r/m] to avoid losing immediately. For fixed G,r,m, let sigma (G,m,r) be the least s such that RSG is won by the spies. Say that $G$ is spy-good if sigma (G,m,r)=[r/m] for all m and r such that r/m less than |V(G)|. We obtain a large class of spy-good graphs. A webbed tree is a graph G having a rooted spanning tree T such that every edge of G not in T joins vertices having the same parent in T.
Theorem. Every webbed tree is spy-good. Furthermore, all graphs having a dominating vertex are webbed trees.
We also consider the game on hypercubes, unicyclic graphs, large k-partite graphs and graphs with small domination number.
This is joint work with Jane V. Butterfield, Gregory J. Puleo, Clifford D. Smyth, Douglas B. West and Reza Zamani.
Contact
[[gyu, Gexin Yu]]