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 = \Theta(n^{x})$ for fixed $x \in (0,1)$.
From: Paweł Prałat [view email]
[v1]
Tue, 15 Jul 2025 19:41:23 UTC (39 KB)
[v2]
Wed, 2 Sep 2026 15:49:33 UTC (39 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。