A note on the localization number of random graphs: diameter two case

DOI10.1016/J.DAM.2018.06.006MaRDI QIDQ1720315zbMATH OpenOpenAlexWikidataFDO

Authors Andrzej Dudek, Wesley Pegden, Alan Frieze

Publication date 8 February 2019

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

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

zbMATH Keywords

random graphslocalization game

Mathematics Subject Classification ID

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

Abstract: We study the localization game on dense random graphs. In this game, a {em cop} $x$ tries to locate a {em robber} $y$ by asking for the graph distance of $y$ from every vertex in a sequence of sets $W_1,W_2,ldots,W_{e}ll$. We prove high probability upper and lower bounds for the minimum size of each $W_i$ that will guarantee that $x$ will be able to locate $y$.

Recommendations

• scientific article; zbMATH DE number 7720720
• An estimate of the probability of localisation of the diameter of a random scale-free graph
• Locality of random digraphs on expanders
• On the diameter of a class of random graphs
• Localization in random geometric graphs with too many edges
• On the graphs with given diameter, number of vertices, and local diversity of balls
• On the locatic number of graphs
• The diameter of a random graph with bounded diameter

Cites work

• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• 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
• The game of cops and robbers on graphs

Cited in

(13)

• Localization game for random geometric graphs
• The localization game on oriented graphs
• The localization capture time of a graph
• An estimate of the probability of localisation of the diameter of a random scale-free graph
• Bounds on the localization number
• Localization game for random graphs
• Hyperopic cops and robbers
• The localization game on Cartesian products
• Effective localization number: Building k-surviving degrees
• The localization number of designs
• Edge and pair queries-random graphs and complexity
• scientific article; zbMATH DE number 7720720 (Why is no real title available?)
• Sequential metric dimension for random graphs

This page was built for publication: A note on the localization number of random graphs: diameter two case

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