Multiset Metric Dimension of Binomial Random Graphs

Abstract

For a graph $G=(V,E)$ and a subset $R\subseteq V$, we say that $R$ is \textit{multiset resolving} for $G$ if for every pair of vertices $v,w$, the \textit{multisets} $\{d(v,r):r\in R\}$ and $\{d(w,r):r\in R\}$ are distinct, where $d(x,y)$ is the graph distance between vertices $x$ and $y$. The \textit{multiset metric dimension} of $G$ is the size of a smallest set $R\subseteq V$ that is multiset resolving (or $\infty$ if no such set exists). This graph parameter was introduced by Simanjuntak, Siagian, and Vitrík in 2017~\cite{simanjuntak2017multiset}, and has since been studied for a variety of graph families. We prove bounds which hold with high probability for the multiset metric dimension of the binomial random graph $G(n,p)$ in the regime $d=(n-1)p=\hat{I}˜(n^x)$ for fixed $x\in (0,1)$.

15 pages, 1 figure