An evasion game on a graph

DOI10.1016/J.DISC.2013.09.004MaRDI QIDQ383337zbMATH OpenOpenAlexFDO

Authors John Haslegrave

Publication date 3 December 2013

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

treecops and robbersgraph searchingevasion gamepursuit game

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43) Positional games (pursuit and evasion, etc.) (91A24)

Abstract: This paper introduced a pursuit and evasion game to be played on a connected graph. One player moves invisibly around the graph, and the other player must guess his position. At each time step the second player guesses a vertex, winning if it is the current location of the first player; if not the first player must move along an edge. It is shown that the graphs on which the second player can guarantee to win are precisely the trees that do not contain a particular forbidden subgraph, and best possible capture times on such graphs are obtained.

Recommendations

• On evasion games on graphs
• On a pursuit game played on graphs for which a minor is excluded
• On a characterization of evasion strategies for pursuit-evasion games on graphs
• Pursuit—Evasion games on graphs
• scientific article; zbMATH DE number 3918143

Cites work

• scientific article; zbMATH DE number 1792626 (Why is no real title available?)
• A game of cops and robbers
• Cops and robbers in graphs with large girth and Cayley graphs
• Locating a robber on a graph
• Locating a robber on a graph via distance queries
• Vertex-to-vertex pursuit in a graph

Cited in

(24)

• Pursuit—Evasion games on graphs
• On evasion games on graphs
• Locating a robber with multiple probes
• On a pursuit-evasion model without instantaneous movement
• Searching for an intruder on graphs and their subdivisions
• Subdivisions in the robber locating game
• The explorer-director game on graphs
• Approximately locating an invisible agent in a graph with relative distance queries
• A robber locating strategy for trees
• The cat and the noisy mouse
• Pursuit-evasion games of multiple cooperative pursuers and an evader: a biological-inspired perspective
• Formulation of a cooperative-confinement-escape problem of multiple cooperative defenders against an evader escaping from a circular region
• How to hunt an invisible rabbit on a graph
• A pursuit-evasion problem on a grid
• Search for a moving target in a graph
• On a characterization of evasion strategies for pursuit-evasion games on graphs
• Finding a princess in a palace: a pursuit-evasion problem
• The robber locating game
• An evasion game with a destination
• On a pursuit game played on graphs for which a minor is excluded
• scientific article; zbMATH DE number 2086681 (Why is no real title available?)
• Randomized Pursuit-Evasion in Graphs
• On the Cookie-Cutter Game: Search and Evasion on a Disc
• The guarding game is E-complete

This page was built for publication: An evasion game on a graph

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