Localization game for random geometric graphs

DOI10.1016/J.EJC.2022.103616zbMATH Open1504.05192arXiv2102.10352OpenAlexW3131033879MaRDI QIDQ2107488FDOQ2107488

Authors: Lyuben Lichev, Paweł Prałat, D. Mitsche 

Publication date: 1 December 2022

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: The localization game is a two player combinatorial game played on a graph $G=(V,E)$. The cops choose a set of vertices $S_{1}subseteqV$ with $|S_1|=k$. The robber then chooses a vertex $vinV$ whose location is hidden from the cops, but the cops learn the graph distance between the current position of the robber and the vertices in $S_1$. If this information is sufficient to locate the robber, the cops win immediately; otherwise the cops choose another set of vertices $S_{2}subseteqV$ with $|S_2|=k$, and the robber may move to a neighbouring vertex. The new distances are presented to the robber, and if the cops can deduce the new location of the robber based on all information they accumulated thus far, then they win; otherwise, a new round begins. If the robber has a strategy to avoid being captured, then she wins. The localization number is defined to be the smallest integer $k$ so that the cops win the game. In this paper we determine the localization number (up to poly-logarithmic factors) of the random geometric graph $GinmathcalG(n,r)$ slightly above the connectivity threshold.

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

Recommendations

• Localization game on geometric and planar graphs
• The localization game on oriented graphs
• Localization in random geometric graphs with too many edges
• GEODETIC GAMES FOR GRAPHS
• Positional games on random graphs
• scientific article; zbMATH DE number 4035609
• The localization game on Cartesian products
• scientific article; zbMATH DE number 3970795
• A sequential locating game on graphs

Mathematics Subject Classification ID

Geometric probability and stochastic geometry (60D05) Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43)

Cites Work

• Random Geometric Graphs
• Title not available (Why is that?)
• The isoperimetric inequality
• Generalized curvatures
• The longest edge of the random minimal spanning tree
• Locating a robber on a graph via distance queries
• Locating a robber on a graph
• Metric dimension for random graphs
• Locating a robber with multiple probes
• Locating a backtracking robber on a tree
• An extension of the Hoeffding inequality to unbounded random variables
• Localization game on geometric and planar graphs
• A robber locating strategy for trees
• Localization game for random graphs
• A note on the localization number of random graphs: diameter two case
• On the relation between graph distance and Euclidean distance in random geometric graphs
• Bounds on the localization number

Cited In (2)

• The localization game on oriented graphs
• Edge and pair queries-random graphs and complexity

This page was built for publication: Localization game for random geometric graphs

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