Multiset Metric Dimension of Binomial Random Graphs

For a graph $G=(V,E)$ and a subset $R\subseteq V$, we say that $R$ is $\mathit{\text{multiset}}\mathit{\text{resolving}}$ for $G$ if for every pair of vertices $v,w$, the $\mathit{\text{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 $\mathit{\text{multiset}}\mathit{\text{metric}}\mathit{\text{dimension}}$ of $G$ is the size of a smallest set $R\subseteq V$ that is multiset resolving (or $\mathrm{\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=\mathrm{\Theta }(n^x)$ for fixed $x\in (0,1)$.