Multiset metric dimension of binomial random graphs
Austin Eide, Paweł Prałat · Discrete Applied Mathematics · 2026
For a graph G = ( V , E ) and a subset R ⊆ V , we say that R is multiset resolving for G if for every pair of vertices v , w , the multisets [ d ( v , r ) : r ∈ R ] and [ d ( w , r ) : r ∈ R ] are distinct, where d ( x , y ) is the graph distance between vertices x and y . The multiset metric dimension of G is the size of a smallest set R ⊆ V that is multiset resolving (or ∞ if no such set exists). This graph parameter was introduced by Simanjuntak, Siagian, and Vitrík in 2017 Rinovia Simanjuntak et al. (2017), 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 = Θ ( n x ) for fixed x ∈ ( 0,1 ) .