An Exact Determination of the Radio Number of Graph Hn for n≥15

Suppose that G is a connected graph. For any two vertices u and v, let dG (u,v) denote the distance between u and v in G. The diameter of G is the maximum distance between any pair of vertices, and it is denoted by diamG. A multilevel distance labeling (or radio condition) for G is a function f that assigns to each vertex of G a positive integer such that for any distinct vertices u and v, du,v+fu−fv≥diamG+1. The largest positive integer in the range of f is called the span of f. The radio number of G is denoted by rnG, is the minimum span of a multilevel distance labeling for G. In this paper the multilevel distance labeling of Hn is calculated for every n≥15: rnHn=4n+2.