On Radio Labeling of Diameter N-2 and Caterpillar Graphs

Radio labeling of graphs is a specific type of graph labeling. Radio labeling evolved as a way to use graph theory to try to solve the channel assignment problem: how to assign radio channels so that two radio transmitters that are relatively close to one another do not have frequencies that cause interference between them. This problem of channel assignment was first put into a graph theoretic context by Hale. In terms of graph theory, the vertices of a graph represent the locations of the radio transmitters, or radio stations, with the labels of the vertices corresponding to channels or frequencies assigned to the stations.

Different restrictions on labelings of graphs have been studied to address the channel assignment problem. Radio labeling of a simple connected graph G is a labeling f from the vertex set of G to the positive integers such that for every pair of distinct vertices u and v of G, distance(u,v) + |f(u)-f(v)| is greater than or equal to diameter(G) +1. The largest number used to label a vertex of G is called the span of the labeling. The radio number of G is the smallest possible span for a radio labeling of G. The radio numbers of certain families of graphs have already been found. In particular, bounds and radio numbers of some tree graphs have been determined. Daphne Der-Fen Liu and Xuding Zhu determined the radio number of paths and Daphne Der-Fen Liu found a general lower bound for the radio number of trees.

This thesis builds off of work done on paths and trees in general to determine an improved lower bound or the actual radio number of certain graphs. This thesis includes joint work with Matthew Porter and Maggy Tomova on determining the radio numbers of graphs with n vertices and diameter n-2. This thesis also establishes the radio number of some specific caterpillar graphs as well as an improved lower bound for the radio number of more general caterpillar graphs.