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

Institutions

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-09-19
DOI
https://doi.org/10.5281/zenodo.22843683
Primary Topic
Graph Labeling and Dimension Problems
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
preprint

Edge multiset dimension of subdivided complete graphs

Pedro M. M. de Castro
Zenodo (CERN European Organization for Nuclear Research)
Graph Labeling and Dimension Problems
preprint

Edge multiset dimension of subdivided complete graphs

Pedro M. M. de Castro
preprint en

Abstract

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.

Zenodo (CERN European Organization for Nuclear Research)
Universidade Federal de Pernambuco (BR)
Sustainable cities and communities
Graph Labeling and Dimension Problems
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Edge multiset dimension of subdivided complete graphs — Pedro M. M. de Castro · Zenodo (CERN European Organization for Nuclear Research) (2026) | TGRS Research Map | TGRS