2025/07/15 by Austin Eide, Eide, Austin, Paweł Prałat +1
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Data Management and Algorithms #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.2507.11686
openalex publication_date 2025/07/15 · openalex created_date 2025/10/14 · openalex updated_date 2026/07/28
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~\citesimanjuntak2017multiset, 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 = Θ(nx) for fixed x ∈ (0,1).