Abstract

For a simple finite connected graph $G$, let $\diam(G)$ and $d_{G}(u,v)$ denote the diameter of $G$ and distance between $u$ and $v$ in $G$, respectively. A radio labeling of a graph $G$ is a mapping $f$ : $V(G)$ $\rightarrow$ \{0, 1, 2,...\} such that $|f(u)-f(v)|\geq \diam(G) + 1 - d_{G}(u,v)$ holds for every pair of distinct vertices $u,v$ of $G$. The radio number $\rn(G)$ of $G$ is the smallest number $k$ such that $G$ has radio labeling $f$ with max$\{f(v):v \in V(G)\}$ = $k$. Bantva {\it et al.} gave a lower bound for the radio number of trees in [1, Lemma 3.1] and, a necessary and sufficient condition to achieve this lower bound in [1, Theorem 3.2]. Denote the lower bound for the radio number of trees given in [1, Lemma 3.1] by $lb(T)$. A tree $T$ is called a lower bound tree for the radio number if $\rn(T)$ = $lb(T)$. In this paper, we construct some large lower bound trees for the radio number using known lower bound trees.

Keywords and Phrases

Interference, channel assignment, radio labeling, radio number, tree.

A.M.S. subject classification

05C78, 05C15, 05C12.

.....