PreprintCC BY 4.0arXiv
On Multi-label radio Labelings of Graphs
Abstract
We propose and study a multi-labeling generalization of the k-radio labeling problem of graphs: given a graph G and integers k and m, assign to each vertex of G a set of m integer labels such that distinct labels assigned to a vertex differ by at least k+1, and the labels of any two distinct vertices x and y pairwise differ by at least k+1−d(x,y), with d(x,y) being the distance between vertices x and y. We prove general bounds on the minimum span of such a labeling and more refined results for the case k=1. For paths and cycles, we derive sharp bounds on the minimum span when k is small. We finally propose a conjecture for the minimum span on the path and for an almost-tight bound on the cycle.
Related
- Algebraic characterizations of generating and affinely generating Γ-magic maps and Γ-distance magic labelings on regular graphs
- Prime Labelings of Trees
- Efficient Discrete Multi-View Clustering with Tensorized Label Learning
- On a conjecture concerning antipodal labelings for cycles
- SymNetPro: LOS-Aware Directional Multi-Transmitter Localization from Sparse Radio Observations
BibTeX
@misc{togni2026multilabel,
title = {{On Multi-label radio Labelings of Graphs}},
author = {Olivier Togni},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.25863},
eprint = {2610.25863},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.25863},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - On Multi-label radio Labelings of Graphs
AU - Olivier Togni
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2610.25863
UR - https://arxiv.org/abs/2610.25863
AB - We propose and study a multi-labeling generalization of the k-radio labeling problem of graphs: given a graph G and integers k and m, assign to each vertex of G a set of m integer labels such that distinct labels assigned to a vertex differ by at least k+1, and the labels of any two distinct vertices x and y pairwise differ by at least k+1−d(x,y), with d(x,y) being the distance between vertices x and y. We prove general bounds on the minimum span of such a labeling and more refined results for the case k=1. For paths and cycles, we derive sharp bounds on the minimum span when k is small. We finally propose a conjecture for the minimum span on the path and for an almost-tight bound on the cycle.
ER -