math.CO — Combinatorics

Edge multiset dimension of subdivided complete graphs

Contributed by Pedro Machado Manhães de Castro

An edge of a graph can be identified by its distances to a suitable set of vertices. If the reports omit the names of these vertices, only a multiset of distances remains, and finding a suitable set becomes more difficult. We determine the asymptotic cost of this loss of information for subdivided complete graphs. Let $K_n$ be the complete graph on $n\ge3$ vertices, and let $S_L(K_n)$ replace each edge with a path of $L$ edges, where $L\ge2$ is an integer. Let $\operatorname{edim}_{\mathrm m}$ be the minimum number of vertices whose distance multisets distinguish all edges. For every fixed $L\ge3$, we prove $\operatorname{edim}_{\mathrm m}(S_L(K_n))=\Theta_L\!\left(n^{1+1/\lfloor L/2\rfloor}\right) \qquad(n\longrightarrow\infty).$ Retaining the names requires only $\Theta(n)$ vertices. Without them, the cost is quadratic at length three, has order $n^{3/2}$ at lengths four and five, and has smaller exponents at longer fixed lengths. We also settle existence at the two shortest lengths for every $n\ge3$: no selection works at length two, whereas at length three at most $\binom n2$ vertices suffice. The proofs combine a count of integer vectors with realizable vertex labels. Sidon sets distinguish endpoint pairs at odd lengths, and exact finite certificates complete the length-three construction.