Radio labelings of graphs



A radio labeling of a connected graph $G$ is an assignment of distinct positive integers to the vertices of $G$, with $x \in V(G)$ labeled $c(x)$, such that $$d(u, v) + |c(u) - c(v)| \geq 1 + \diam G$$ for every two distinct vertices $u, v$ of $G$, where $\diam G$ is the diameter of $G$. The radio number $rn(c)$ of a radio labeling $c$ of $G$ is the maximum label assigned to a vertex of $G$. The radio number $rn(G)$ of $G$ is $\min\{rn(c)\}$ over all radio labelings $c$ of $G$. The radio numbers of some well known graphs are studied. It is shown that if $G$ is a connected graph of order $n$ and diameter $2$, then $n \leq rn(G) \leq 2n-2$ and that for every pair $k, n$ of integers with $n \leq k \leq 2n-2$, there exists a connected graph of order $n$ and diameter $2$ with $rn(G) = k$. A characterization of connected graphs of order $n$ and diameter $2$ with prescribed radio number is presented.