The cat and the noisy mouse

DOI10.1016/J.DISC.2018.01.009MaRDI QIDQ1699546zbMATH OpenOpenAlexFDO

Authors Dieter Rautenbach, Moritz Schneider

Publication date 23 February 2018

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

pursuit and evasion game

Mathematics Subject Classification ID

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

Abstract: We consider a variant of a pursuit and evasion game studied independently by Britnell and Wildon as well as Haslegrave. In their game, a cat has to catch an invisible mouse that moves along the edges of some graph $G$. In our version, the cat receives partial information about its distance to the mouse, and we show that the cat has a winning strategy if and only if $G$ is a forest. Seager proposed a similar game with complete distance information whose rules cause some small yet important differences to the game we consider.

Recommendations

• An evasion game on a graph
• On evasion games on graphs
• On a pursuit game played on graphs for which a minor is excluded
• On a pursuit game on Cayley digraphs
• scientific article; zbMATH DE number 3918143

Cites work

• A robber locating strategy for trees
• An evasion game on a graph
• Finding a princess in a palace: a pursuit-evasion problem
• Locating a backtracking robber on a tree
• Locating a robber on a graph
• Locating a robber on a graph via distance queries
• The robber locating game

Cited in

(1)

• Approximately locating an invisible agent in a graph with relative distance queries

This page was built for publication: The cat and the noisy mouse

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