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

Institutions

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
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

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.

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