#### Document Type

Dissertation

#### Date of Degree

Summer 2013

#### Degree Name

PhD (Doctor of Philosophy)

#### Degree In

Mathematics

#### First Advisor

Maggy Tomova

#### Abstract

For *k*∈{Z}^{+} and *G* a simple connected graph, a *k*-radio labeling *f*:V_{G}→Z^{+} of *G* requires all pairs of distinct vertices *u* and *v* to satisfy |*f*(*u*)-*f*(*v*)|≥ *k*+1-*d*(*u*,*v*). When *k*=1, this requirement gives rise to the familiar labeling known as vertex coloring for which each vertex of a graph is labeled so that adjacent vertices have different "colors". We consider *k*-radio labelings of *G* when *k*=diam(*G*). In this setting, no two vertices can have the same label, so graphs that have radio labelings of consecutive integers are one extreme on the spectrum of possibilities; graphs that can be labeled with such a labeling are called *radio graceful*. In this thesis, we give four main results on the existence of radio graceful graphs, which focus on Hamming graphs (Cartesian products of complete graphs) and a generalization of the Petersen graph. In particular, we prove the existence of radio graceful graphs of arbitrary diameter, a result previously unknown. Two of these main results show that, under certain conditions, the *t*^{th} Cartesian power *G*^{t} of a radio graceful graph *G* is also radio graceful. We will also speak to occasions when *G*^{t} is not radio graceful despite *G* being so, as well as some partial results about necessary and sufficient conditions for a graph *G* so that *G*^{t} is radio graceful.

#### Keywords

Cartesian product of graphs, Hamming graphs, radio graceful graphs, radio labeling

#### Pages

vii, 76 pages

#### Bibliography

Includes bibliographical references (pages 74-76).

#### Copyright

Copyright 2013 Amanda Jean Niedzialomski