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.

Keywords and Phrases

Radio labeling, radio number, tree.

A.M.S. subject classification

05C12, 05C15, 05C78.

.....