Graph labeling methods improve distance-based label assignment limits
On Multi-label radio Labelings of Graphs
Discrete Mathematics
Summary
The paper looks at a way to label points in a network with multiple numbers each, following rules that keep these numbers sufficiently different based on how close the points are. The authors explore general guidelines on how to do this efficiently, especially focusing on simple networks like lines and circles. They provide exact best ways to assign labels in some cases and suggest new predictions for unclear situations. This helps understand how to organize multiple labels that respect distance constraints in networks.
What this means in practice
- •For network schedulers: Set frequency assignments in networks with strict spacing requirements to avoid interference based on node distances.
- •For wireless network engineers: Design address or channel labelings for network nodes that require multiple distinct signals spaced by distance constraints.
A theory result. No direct application yet.
Authors
Olivier Togni
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.