IJPAM: Volume 71, No. 2 (2011)

UPPER BOUNDS ON THE RADIO NUMBER OF SOME TREES

P. Venkata Subba Reddy$^1$, K. Viswanathan Iyer$^2$
$^{1,2}$Department of Computer Science and Engineering
National Institute of Technology
Tiruchirapalli, 620015, Tamil Nadu, INDIA


Abstract. Let $G$ be a simple,connected and undirected graph with diameter $d$. For a positive integer $k\;(\leq d)$, a radio $k$-labeling $f$ of $G$ is an assignment of non-negative integers, called labels to the vertices of $G$ such that if $u,v \in V(G)$ are distinct then $d(u, v) + \vert f(u) - f(v)\vert \geq k + 1$ where $d(u,v)$ is the distance between $u$ and $v$. The maximum label (positive integer) assigned by $f$ to some vertex of $G$ is called the span of $f$. The radio number of $G$ denoted by $rn(G)$ is the minimum span over all radio $d$-labelings of $G$. In this paper, we prove an upper bound for the radio number of binomial tree, Fibonacci trees and uniform caterpillar.

Received: April 15, 2011

AMS Subject Classification: 05C12, 05C15, 05C78

Key Words and Phrases: radio labeling, radio number, binomial tree, Fibonacci tree and uniform caterpillar

Download paper from here.


Source: International Journal of Pure and Applied Mathematics
ISSN printed version: 1311-8080
ISSN on-line version: 1314-3395
Year: 2011
Volume: 71
Issue: 2