Sequential metric dimension for random graphs

DOI10.1017/JPR.2021.16MaRDI QIDQ5014301zbMATH OpenOpenAlexFDO

Authors Gergely Ódor, Patrick Thiran

Publication date 1 December 2021

Published in Journal of Applied Probability (Search for Journal in Brave)

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

zbMATH Keywords

source detectionbinary search on graphsexpansion properties of Erdős-Rényi graphssequential metric dimensoin

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Combinatorics in computer science (68R05) Combinatorial probability (60C05)

Abstract: In the localization game on a graph, the goal is to find a fixed but unknown target node $v^{s}tar$ with the least number of distance queries possible. In the $j^{th}$ step of the game, the player queries a single node $v_j$ and receives, as an answer to their query, the distance between the nodes $v_j$ and $v^{s}tar$. The sequential metric dimension (SMD) is the minimal number of queries that the player needs to guess the target with absolute certainty, no matter where the target is. The term SMD originates from the related notion of metric dimension (MD), which can be defined the same way as the SMD, except that the player's queries are non-adaptive. In this work, we extend the results of cite{bollobas2012metric} on the MD of ErdH{o}s-R'enyi graphs to the SMD. We find that, in connected ErdH{o}s-R'enyi graphs, the MD and the SMD are a constant factor apart. For the lower bound we present a clean analysis by combining tools developed for the MD and a novel coupling argument. For the upper bound we show that a strategy that greedily minimizes the number of candidate targets in each step uses asymptotically optimal queries in ErdH{o}s-R'enyi graphs. Connections with source localization, binary search on graphs and the birthday problem are discussed.

Recommendations

• Metric dimension for random graphs
• Asymptotic behavior of the edge metric dimension of the random graph
• On the limiting distribution of the metric dimension for random forests
• Sequential metric dimension
• Sequential metric dimension

Cites work

• scientific article; zbMATH DE number 3494441 (Why is no real title available?)
• scientific article; zbMATH DE number 3544092 (Why is no real title available?)
• scientific article; zbMATH DE number 3245540 (Why is no real title available?)
• A correlation inequality and a poisson limit theorem for nonoverlapping balanced subgraphs of a random graph
• A note on the localization number of random graphs: diameter two case
• A sequential locating game on graphs
• Approximations to the birthday problem with unequal occurrence probabilities and their application to the surname problem in Japan
• Codes identifying sets of vertices in random networks
• Deterministic and probabilistic binary search in graphs
• Identifying codes and searching with balls in graphs
• Metric dimension for random graphs
• New versions of Suen's correlation inequality
• On a new class of codes for identifying vertices in graphs
• On random ±1 matrices: Singularity and determinant
• On the Metric Dimension of Cartesian Products of Graphs
• On the Probability That a Random ± 1-Matrix Is Singular
• On the limiting distribution of the metric dimension for random forests
• On the singularity of random Bernoulli matrices -- novel integer partitions and lower bound expansions
• Rumors in a Network: Who's the Culprit?
• Sequential metric dimension
• The Geometry of Generalized Binary Search
• Two moments suffice for Poisson approximations: The Chen-Stein method

Cited in

(7)

• Metric dimension for random graphs
• The power of adaptivity in source identification with time queries on the path
• Localization game for random graphs
• On the robustness of the metric dimension of grid graphs to adding a single edge
• A note on robber locating game
• Sequential metric dimension
• Sequential metric dimension

This page was built for publication: Sequential metric dimension for random graphs

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