Vertex-to-vertex pursuit in a graph

1983/01/01 by Richard Nowakowski, Richard J. Nowakowski, Peter Winkler · 601 citations
Computer Science · Mathematics · Social Sciences · #Artificial Intelligence in Games #Combinatorics #Digital Games and Media #Discrete mathematics #Graph #Mathematics #Neighbourhood (mathematics) #Teaching and Learning Programming #Vertex (graph theory)

paper · doi:10.1016/0012-365x(83)90160-7

published in Discrete Mathematics 43(2-3), 235-239 (Elsevier BV)

openalex publication_date 1983/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/10

Cited by

• The 2-Cops-Move Cop Number of Graphs on the Torus, Klein Bottle, and Projective Plane
• The Zombie Damage Number of a Graph
• Domain Design for the Cops and Robbers Problem
• Cops and robbers, clique covers, and induced cycles
• Throttling numbers for adversaries on connected graphs
• A note on bounds for the cop number using tree decompositions
• Greedy Strategies and Larger Islands of Tractability for Conjunctive Queries and Constraint Satisfaction Problems
• A cop-robber game on metric graphs
• Structure of (bull, diamond)-free graphs and its applications
• Are Large Random Graphs Always Safe to Hide?
• Leader Election via Unique Sink Orientation
• Cops and Robbers on diameter two graphs
• On the Cop Number of a Graph
• Mixing Homomorphisms, Recolourings, and Extending Circular Precolourings
• A study of cops and robbers in oriented graphs
• Deduction with k moves
• Hyperopic Cops and Robbers
• Lazy Cops and Robbers played on Graphs
• Cop number of partial cubes
• Cop number of 2K₂-free graphs
• Finding a princess in a palace: A pursuit-evasion problem
• The 3x3 rooks graph is the unique smallest graph with lazy cop number 3
• Monophonic number of Kneser graphs and strongly 2-monophonic graphs
• Cops, robbers, and infinite graphs
• Cops and Robbers on Graphs with Path Constraints
• The capture time in the game of cops and many robbers
• Capturing an Invisible Robber using Separators
• Limited-visibility Cops and Robbers on Hamming graphs
• All Ordinals are Cop-Robber Ordinals
• Recent Progress in Graph Pebbling
• The damage throttling number of a graph
• Searching the Nodes of a Graph: Theory and Algorithms
• Markov models for the tipsy cop and robber game on graphs
• The guarding game is E-complete
• Fully Active Cops and Robbers
• A Cop-Win Graph with Maximum Capture Time ω
• Undecidability of the block gluing classes of homshifts
• The Petersen graph is the smallest 3-cop-win graph
• The capture time of the hypercube
• Cops and Robbers, Clique Covers, and Induced Cycles
• A Sublinear Bound on the Cop Throttling Number of a Graph
• An application of the Gyárfás path argument
• Small Connected Planar Graph with 1-Cop-Move Number 4
• Reasoning under uncertainty in the game of Cops and Robbers
• Chasing robbers on random geometric graphs---an alternative approach
• Approximating the position of a hidden agent in a graph
• Seeing is not believing in limited visibility cops and robbers
• Playing Snake on a Graph
• Accelerated Cops and Robbers
• Containment: A Variation of Cops and Robbers
• Models of on-line social networks
• Cops and Robbers is EXPTIME-complete
• Line-of-Sight Pursuit in Monotone and Scallop Polygons
• Revolutionaries and Spies
• The game of Overprescribed Cops and Robbers played on graphs
• A new bound for the cops and robbers problem
• An Algorithm for Limited Visibility Graph Searching
• 4K₁-free graph with the cop number 3
• The Cop Number of Graphs with Forbidden Induced Subgraphs
• Cops and robber on grids and tori
• Subgraphs and Colourability of Locatable Graphs
• Strong spatial mixing in homomorphism spaces
• Characterizations and algorithms for generalized Cops and Robbers games
• To catch a falling robber
• An annotated bibliography on guaranteed graph searching
• Scalable and practical pursuit-evasion with networked robots
• The node cop-win reliability of unicyclic and bicyclic graphs
• The role of quantum correlations in Cop and Robber game
• Meyniel’s conjecture on the cop number: A survey
• An Optimized Evacuation Plan for an Active-Shooter Situation Constrained by Network Capacity
• On the minimum order of k-cop win graphs
• A Dynamic location problem for graphs
• Graph homomorphisms: structure and symmetry
• Clique Graphs of Chordal and Path Graphs
• Visibility graphs, dismantlability, and the cops and robbers game
• Cops and Robber on Cartesian products and some classes of hypergraphs
• Graph Homomorphism Reconfiguration and Frozen H-Colourings
• A Covering Pursuit Game
• Cops and Robbers for Graphs on Surfaces with Crossings
• Pursuit–evasion [wikipedia]
• The effectiveness of naive optimization of the egress path for an active-shooter scenario. [europepmc]