Revolutionaries and spies on trees and unicyclic graphs

DOI10.4310/JOC.2012.V3.N2.A4zbMATH Open1262.05024arXiv1110.2274MaRDI QIDQ1937355FDOQ1937355

Authors: Daniel W. Cranston, Clifford Smyth, Douglas B. West 

Publication date: 28 February 2013

Published in: Journal of Combinatorics (Search for Journal in Brave)

Abstract: 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)|,FLr/m$ spies are needed. When $G$ is a tree, this many spies suffices. When $G$ is a unicyclic graph, $min|V(G)|,CLr/m$ spies suffice, and we characterize those unicyclic graphs where $FLr/m+1$ spies are needed. defFL#1{lfloor #1 floor} defCL#1{lceil #1 ceil}

Full work available at URL: https://arxiv.org/abs/1110.2274

Recommendations

• Revolutionaries and spies
• Revolutionaries and spies: spy-good and spy-bad graphs
• Revolutionaries and Spies on Random Graphs
• Spy-game on graphs
• Spy-game on graphs: complexity and simple topologies

zbMATH Keywords

unicyclic graphcops and robberpursuit gamerevolutionaries and spies

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Games on graphs (graph-theoretic aspects) (05C57)

Cited In (4)

• Revolutionaries and Spies on Random Graphs
• Revolutionaries and spies
• Revolutionaries and spies: spy-good and spy-bad graphs
• On the intersection of all critical sets of a unicyclic graph

This page was built for publication: Revolutionaries and spies on trees and unicyclic graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1937355)