Radio number of trees

Abstract

A radio labeling of a graph $G$ is a mapping $f:V(G)\to \{0,1,2,\dots \}$ such that $|f(u)-f(v)|\ge d+1-d(u,v)$ for every pair of distinct vertices $u,v$ of $G$, where $d$ is the diameter of $G$ and $d(u,v)$ the distance between $u$ and $v$ in $G$. The radio number of $G$ is the smallest integer $k$ such that $G$ has a radio labeling $f$ with $\max \{f(v):v\in V(G)\}=k$. We give a necessary and sufficient condition for a lower bound on the radio number of trees to be achieved, two other sufficient conditions for the same bound to be achieved by a tree, and an upper bound on the radio number of trees. Using these, we determine the radio number for three families of trees.

19 pages, 7 figures. This is the final version accepted in Discrete Applied Mathematics