ON LOWER BOUND TREES FOR THE RADIO NUMBER

Abstract

A radio labeling of a graph $G$ is a function $f$ from the set of vertices $V(G)$ to the set of non-negative integers such that $|f(u)-f(v)|\geq \diam(G) + 1 - d(u,v)$ for every pair of distinct vertices $u,v$ of $G$. The radio number of $G$, denoted by $\rn(G)$, is the smallest number $k$ such that $G$ has radio labeling $f$ with max$\{f(v):v \in V(G)\}$ = $k$. In [11, Theorem 3], Liu gave a lower bound for the radio number of trees and presented a class of trees, namely spiders, achieving the lower bound. A tree $T$ is called a lower bound tree for the radio number if the radio number of $T$ is equal to the lower bound given in [11, Theorem 3]. In this paper, we give two techniques which convert any tree to lower bound tree for the radio number by adding new vertices to given tree.