Multilevel Distance Labelings for Paths and Cycles

Source abstract

For a graph G, let $\diam(G)$ denote the diameter of G. For any two vertices u and v in G, let $d(u, v)$ denote the distance between u and v. A multilevel distance labeling (or distance labeling) for G is a function f that assigns to each vertex of G a nonnegative integer such that for any vertices u and v, $|f(u)-f(v)| \geq \diam(G) - d_G(u, v) +1$. The span of f is the largest number in $f(V)$. The radio number of G, denoted by $rn(G)$, is the minimum span of a distance labeling for G. In this paper, we completely determine the radio numbers for paths and cycles.