Radio Number for Total Graph of Paths

A radio labeling of a graph is a function from the vertex set to the set of nonnegative integers such that , where and are diameter and distance between and in graph , respectively. The radio number of is the smallest number such that has radio labeling with . We investigate radio number for total graph of paths. 1. Introduction In a telecommunication system to design radio networks, the interference constraints between a pair of transmitters play a vital role. For the transmitters of radio network, we seek to assign channels such that the network fulfills all the interference constraints. The assignment of channels to the transmitters is popularly known as channel assignment problem which was introduced by Hale [1]. For radio network if we assume that the frequencies are uniformly distributed in the spectrum then the frequency span determines the bandwidth allocated for the assignment. In this case, the interference between two transmitters is closely related with the geographic location of the transmitters. Earlier designer of radio networks considered only the two-level interference, namely, major and minor. They classified a pair of transmitters as very close transmitters if the interference level between them is major and close transmitters if the interference level between them is minor. To solve the channel assignment problem, the interference graph is developed and assignment of channels converted into graph labeling (a graph labeling is an assignment of label to each vertex according to certain rule). In interference graph, the transmitters are represented by the vertices, and two vertices are joined by an edge if corresponding transmitters have the major interference while two transmitters have minor interference then corresponding vertices are at distance two, and there is no interference between transmitters if they are at distance three or beyond it. In other words, very close transmitters are represented by adjacent vertices, and close transmitters are represented by the vertices which are at distance two apart. In fact, Roberts [2] proposed that a pair of transmitters which has minor interference must receive different channels and a pair of transmitters which has major interference must receive channels that are at least two apart. Motivated through this problem Griggs and Yeh [3] introduced -labeling in which channels are related with the nonnegative integers. Definition 1. A distance two labeling (or -labeling) of a graph is a function from vertex set to the set of nonnegative integers such that the following conditions are