The one-visibility localization game

DOI10.1016/J.TCS.2023.114186MaRDI QIDQ6073890zbMATH OpenOpenAlexFDO

Authors Anthony Bonato, Trent Gregory Marbach, Michael Molnar, JD Nir

Publication date 12 October 2023

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

graphsisoperimetric inequalitieslimited visibilitylocalization numberpursuit-evasion games

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: We introduce a variant of the Localization game in which the cops only have visibility one, along with the corresponding optimization parameter, the one-visibility localization number $zet{a}_1$. By developing lower bounds using isoperimetric inequalities, we give upper and lower bounds for $zet{a}_1$ on $k$-ary trees with $kge2$ that differ by a multiplicative constant, showing that the parameter is unbounded on $k$-ary trees. We provide a $O(sqrtn)$ bound for $K_h$-minor free graphs of order $n$, and we show Cartesian grids meet this bound by determining their one-visibility localization number up to four values. We present upper bounds on $zet{a}_1$ using pathwidth and the domination number and give upper bounds on trees via their depth and order. We conclude with open problems.

Cites work

• A lower bound for the vertex boundary-width of complete \(k\)-ary trees
• A note on isoperimetric peaks of complete trees
• A robber locating strategy for trees
• A Separator Theorem for Nonplanar Graphs
• An invitation to pursuit-evasion games and graph theory
• Bounds on isoperimetric values of trees
• Centroidal localization game
• Compressions and isoperimetric inequalities
• Computing the one-visibility cop-win strategies for trees
• scientific article; zbMATH DE number 1303526 (Why is no real title available?)
• scientific article; zbMATH DE number 6820278 (Why is no real title available?)
• scientific article; zbMATH DE number 3997549 (Why is no real title available?)
• scientific article; zbMATH DE number 7720720 (Why is no real title available?)
• Limited visibility cops and robber
• Localization game on geometric and planar graphs
• Locating a backtracking robber on a tree
• Locating a robber on a graph
• Locating a robber on a graph via distance queries
• One-visibility cops and robber on trees
• One-visibility cops and robber on trees: optimal cop-win strategies
• Searching for an intruder on graphs and their subdivisions
• The complexity of zero-visibility cops and robber
• The game of cops and robbers on graphs
• The localization capture time of a graph
• Zero-visibility cops and robber and the pathwidth of a graph

This page was built for publication: The one-visibility localization game

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