Localization game for random graphs

DOI10.1016/J.DAM.2021.12.002MaRDI QIDQ2065786zbMATH OpenOpenAlexFDO

Authors Andrzej Dudek, Sean English, Calum MacRury, Paweł Prałat, Alan Frieze

Publication date 13 January 2022

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

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

zbMATH Keywords

cops and robbersbinomial random graphslocalization number

Mathematics Subject Classification ID

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

Abstract: We consider the localization game played on graphs in which a cop tries to determine the exact location of an invisible robber by exploiting distance probes. The corresponding graph parameter $zeta(G)$ for a given graph $G$ is called the localization number. In this paper, we improve the bounds for dense random graphs determining an asymptotic behaviour of $zeta(G)$. Moreover, we extend the argument to sparse graphs.

Recommendations

• A note on the localization number of random graphs: diameter two case
• Localization game for random geometric graphs
• The localization game on oriented graphs
• Bounds on the localization number
• Localization game on geometric and planar graphs

Cites work

• scientific article; zbMATH DE number 3544092 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• A note on the localization number of random graphs: diameter two case
• A robber locating strategy for trees
• A sequential locating game on graphs
• Bounds on the localization number
• Centroidal localization game
• 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
• Metric dimension for random graphs
• Paths in graphs
• Sequential metric dimension
• Sequential metric dimension for random graphs

Cited in

(9)

• Localization game for random geometric graphs
• Localization game on geometric and planar graphs
• The localization game on oriented graphs
• The localization capture time of a graph
• Bounds on the localization number
• The localization game on Cartesian products
• A sequential locating game on graphs
• The localization number of designs
• Edge and pair queries-random graphs and complexity

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

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