Localization game for random graphs

DOI10.1016/J.DAM.2021.12.002zbMATH Open1480.05092arXiv1910.11225OpenAlexW4206215390MaRDI QIDQ2065786FDOQ2065786

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)

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Paths in graphs
• Title not available (Why is that?)
• Locating a robber on a graph via distance queries
• Locating a robber on a graph
• Metric dimension for random graphs
• Sequential metric dimension for random graphs
• Locating a robber with multiple probes
• Locating a backtracking robber on a tree
• Centroidal localization game
• Localization game on geometric and planar graphs
• A robber locating strategy for trees
• A sequential locating game on graphs
• A note on the localization number of random graphs: diameter two case
• Sequential metric dimension
• Bounds on the localization number

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)