Pursuit Games on Graphs

← Back to Domain-Specific Families

Abstractions about pursuit-evasion games played on graphs, including cop number and cop-win graphs, entanglement and eternal domination, and topological games generalizing capture dynamics to abstract spaces.

5 abstractions in this family — domain-specific abstractions that sit near one another in structural-signature space (k-means over structural-signature embeddings). Each is shown with its short description.

• Cop number — The minimum number of pursuers required to guarantee capture of an evader in the standard cops-and-robber game on a graph.
• Cop-win graph — A graph on which one pursuer has a strategy that guarantees capture of one evader in the alternating vertex-movement game.
• Entanglement (graph measure) — A directed-graph complexity measure equal to the least number of cops needed to capture a perpetually moving robber in the entanglement game.
• Eternal dominating set — A set of graph vertices occupied by mobile guards that can respond to every infinite sequence of vertex attacks while remaining a dominating set after each move.
• Topological game — An infinite perfect-information game on a topological space whose moves are points, sets or covers and whose winning condition encodes a topological property.