Variations on cops and robbers
From MaRDI portal
Abstract: We consider several variants of the classical Cops and Robbers game. We treat the version where the robber can move R > 1 edges at a time, establishing a general upper bound of N / alpha ^{(1-o(1))sqrt{log_alpha N}}, where alpha = 1 + 1/R, thus generalizing the best known upper bound for the classical case R = 1 due to Lu and Peng. We also show that in this case, the cop number of an N-vertex graph can be as large as N^{1 - 1/(R-2)} for finite R, but linear in N if R is infinite. For R = 1, we study the directed graph version of the problem, and show that the cop number of any strongly connected digraph on N vertices is at most O(N(log log N)^2/log N). Our approach is based on expansion.
Recommendations
Cites work
- A better bound for the cop number of general graphs
- A game of cops and robbers
- A note on \(k\)-cop, \(l\)-robber games on graphs
- A short note about pursuit games played on a graph with a given genus
- A witness version of the cops and robber game
- An annotated bibliography on guaranteed graph searching
- Chasing robbers on random graphs: zigzag theorem
- Cops and robbers from a distance
- Cops and robbers in a random graph
- Cops and robbers in graphs with large girth and Cayley graphs
- Graph searching and a min-max theorem for tree-width
- scientific article; zbMATH DE number 5241699 (Why is no real title available?)
- scientific article; zbMATH DE number 2187680 (Why is no real title available?)
- Note on a pursuit game played on graphs
- On a game of policemen and robber
- On a pursuit game on Cayley digraphs
- On a pursuit game on Cayley graphs
- On a pursuit game played on graphs for which a minor is excluded
- On Meyniel's conjecture of the cop number
- On the cop number of a graph
- Pursuing a fast robber on a graph
- Randomized Pursuit-Evasion with Local Visibility
- Searching and sweeping graphs: a brief survey
- The complexity of pursuit on a graph
- Vertex-to-vertex pursuit in a graph
Cited in
(48)- Cops and Robber game with a fast robber on expander graphs and random graphs
- 4-cop-win graphs have at least 19 vertices
- The game of cops and eternal robbers
- Cops and robbers on directed and undirected abelian Cayley graphs
- Ambush cops and robbers
- Meyniel extremal families of abelian Cayley graphs
- Capture times in the bridge-burning cops and robbers game
- The game of cops and robbers on directed graphs with forbidden subgraphs
- Catching an infinitely fast robber on a grid
- Containment: a variation of cops and robber
- The one-cop-moves game on graphs with some special structures
- Cops, a fast robber and defensive domination on interval graphs
- Containment game played on random graphs: another zig-zag theorem
- The optimal capture time of the one-cop-moves game
- Catching a fast robber on the grid
- Cops and robbers playing on edges
- To catch a falling robber
- Meyniel's conjecture holds for random graphs
- Variations of cops and robber on the hypercube
- On Meyniel's conjecture of the cop number
- Chasing a fast robber on planar graphs and random graphs
- Cops and robbers on geometric graphs
- A probabilistic version of the game of zombies and survivors on graphs
- Jumping robbers in digraphs
- Lower bounds for the capture time: linear, quadratic, and beyond
- COPS OR ROBBERS — A BISTABLE SOCIETY
- scientific article; zbMATH DE number 4064802 (Why is no real title available?)
- The fast robber on interval and chordal graphs
- Lower bounds for the cop number when the robber is fast
- scientific article; zbMATH DE number 6180528 (Why is no real title available?)
- Lazy cops and robbers on hypercubes
- Conjectures on cops and robbers
- Cops and robber on some families of oriented graphs
- Cops and robbers from a distance
- Cops and robber on oriented graphs with respect to push operation
- Cops and robber on butterflies, grids, and AT-free graphs
- On a generalization of Meyniel's conjecture on the Cops and Robbers game
- Bounding the cop number of a graph by its genus
- Cops and robbers on multi-layer graphs
- Parameterized analysis of the cops and robber problem
- New constructions of Meyniel extremal families of graphs
- Pushing cops and robber on graphs of maximum degree four
- On the cop number and the weak Meyniel conjecture for algebraic graphs
- Catching a robber on a random k-uniform hypergraph
- Capturing an invisible robber using separators
- Bounds on the length of a game of cops and robbers
- Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems
- Chasing robbers on random geometric graphs-an alternative approach
This page was built for publication: Variations on cops and robbers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2891049)
