The localization game on Cartesian products

DOI10.1016/J.DAM.2021.09.010MaRDI QIDQ2235282zbMATH OpenOpenAlexFDO

Authors Jeandré Boshoff, Adriana Roux

Publication date 21 October 2021

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

Full work available at URL https://arxiv.org/abs/2007.15921, http://hdl.handle.net/10019.1/109303

zbMATH Keywords

Cartesian productsdoubly resolving setsimagination strategylocalization gamemetric dimension

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Graph operations (line graphs, products, etc.) (05C76) 2-person games (91A05) Positional games (pursuit and evasion, etc.) (91A24) Games involving graphs (91A43)

Abstract: The localization game is played by two players: a Cop with a team of $k$ cops, and a Robber. The game is initialised by the Robber choosing a vertex $rinV$, unknown to the Cop. Thereafter, the game proceeds turn based. At the start of each turn, the Cop probes $k$ vertices and in return receives a distance vector. If the Cop can determine the exact location of $r$ from the vector, the Robber is located and the Cop wins. Otherwise, the Robber is allowed to either stay at $r$, or move to $r^{\prime }$ in the neighbourhood of $r$. The Cop then again probes $k$ vertices. The game continues in this fashion, where the Cop wins if the Robber can be located in a finite number of turns. The localization number $zeta(G)$, is defined as the least positive integer $k$ for which the Cop has a winning strategy irrespective of the moves of the Robber. In this paper, we focus on the game played on Cartesian products. We prove that $zeta(GsquareH)geqmaxzeta(G),zeta(H)$ as well as $zeta(GsquareH)leqzeta(G)+psi(H)-1$ where $psi(H)$ is a doubly resolving set of $H$. We also show that $zeta(C_{m}square{C}_n)$ is mostly equal to two.

Recommendations

• Localization game for random geometric graphs
• Localization game for random graphs
• The localization game on oriented graphs
• Bounds on the localization number
• Localization game on geometric and planar graphs

Cites work

• A note on the localization number of random graphs: diameter two case
• A robber locating strategy for trees
• Bounds on the localization number
• Centroidal localization game
• Domination game and an imagination strategy
• Landmarks in graphs
• 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
• Locating a robber with multiple probes
• On the Metric Dimension of Cartesian Products of Graphs

Cited in

(6)

• Localization game on geometric and planar graphs
• Localization game for random geometric graphs
• The localization capture time of a graph
• The localization game on oriented graphs
• Runner locating with multiple probes
• Localization game capture time of trees and outerplanar graphs

This page was built for publication: The localization game on Cartesian products

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