An evasion game on a graph

DOI10.1016/J.DISC.2013.09.004zbMATH Open1277.05117arXiv1701.06012OpenAlexW2022012821MaRDI QIDQ383337FDOQ383337

Authors: John Haslegrave 

Publication date: 3 December 2013

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

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)

Cites Work

• Cops and robbers in graphs with large girth and Cayley graphs
• Vertex-to-vertex pursuit in a graph
• A game of cops and robbers
• Locating a robber on a graph via distance queries
• Title not available (Why is that?)
• Locating a robber on 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
• The explorer-director game on graphs
• Subdivisions in the robber locating game
• A robber locating strategy for trees
• Approximately locating an invisible agent in a graph with relative distance queries
• Pursuit-evasion games of multiple cooperative pursuers and an evader: a biological-inspired perspective
• The cat and the noisy mouse
• 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
• Search for a moving target in a graph
• A pursuit-evasion problem on a grid
• 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
• Title not available (Why is that?)
• 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)