Edge multiset dimension of subdivided complete graphs
Distances from an edge to selected vertices, called landmarks, can identify the edge; each distance is measured from its nearer endpoint. We study how many landmarks are needed when the values and their repetitions are retained but the landmark names are removed. In a complete graph on n vertices with each edge replaced by a five-edge path, the n original vertices suffice when names are retained. We prove that the minimum without names, the edge multiset dimension, grows as n√n up to constant factors as n → ∞. Thus forgetting names increases the number required by an unbounded factor. Our construction uses labels whose pair sums identify the path endpoints, and realizes them as landmark counts. For the matching lower bound, a count of integer points in a simplex limits the possible distance records. For sufficiently large n, the construction works at every path length at least five. More positions improve the bounds for each fixed even length at least eight and odd length at least eleven. Preprint. 20 pages, 4 figures, 4 tables.
Authors
- Pedro M. M. de Castro
Institutions
- Universidade Federal de Pernambuco (BR)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-09-19
- DOI
- https://doi.org/10.5281/zenodo.22849765
- Primary Topic
- Graph Labeling and Dimension Problems
- Type
- preprint