Zenodo, preprint, v3.0
Research account
Edge multiset dimension of subdivided complete graphs
How much information is lost when a distance measurement no longer says where it was taken? A landmark is a selected vertex. To identify an edge, measure its distance to each landmark, using the nearer endpoint. If the landmark names are removed, only the distance values and their repetitions remain. Distinct edges can then become indistinguishable.
We study this loss of information in a complete graph on n ≥ 3 vertices whose edges are replaced by paths of L edges. For every fixed L ≥ 3, the minimum number of landmarks without names has order n1+1/⌊L/2⌋ as n grows, with constants depending on L. Retaining the names requires only a linear number. Thus the unnamed cost is quadratic at length three, has order n3/2 at lengths four and five, and has smaller exponents at longer fixed lengths.
The two shortest lengths also have a complete existence answer for every n ≥ 3. No selection works at length two, whereas at length three at most n(n−1)/2 landmarks suffice. The length-three proof combines an analytic construction with exact finite certificates, covering every order.
The proofs connect graph identification with additive constructions and lattice-point counting. Counts of integer vectors give lower bounds, while realizable degrees and matrix margins supply the landmark sets. At odd lengths, Sidon labels distinguish endpoint pairs. The complete preprint is on Zenodo; the companion data repository contains the CSV certificates and reading instructions for Algorithms 1 and 2.