Edge multiset dimension of subdivided complete graphs
A vertex set resolves the edges of a graph by multisets if the multiplicities of distances to its vertices distinguish every edge. We study the minimum size of such a set for complete graphs whose edges are replaced by paths of a common length. When that length is five, we prove that the minimum is of order n3/2, where n is the number of original vertices. For every n ≥ 222, we construct a resolving set with fewer than 24n3/2 + 18n vertices, uniformly over all path lengths at least five. The construction realizes balanced Sidon labels as the margins of two binary matrices and decodes every edge from its distance histogram. For path length five, central edges yield a matching lower bound through a count of lattice points of prescribed cost. A rank lemma for symmetric degree profiles gives smaller upper exponents for even path lengths at least eight and odd path lengths at least eleven. For odd lengths at least seven, a matching lower bound within this symmetric class identifies the limitation of that construction. Preprint. 15 pages, 3 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.22843684
- Primary Topic
- Graph Labeling and Dimension Problems
- Type
- preprint