For k∈{Z}+ and G a simple connected graph, a k-radio labeling f:VG→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 tth Cartesian power Gt of a radio graceful graph G is also radio graceful. We will also speak to occasions when Gt 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 Gt is radio graceful.
| Identifer | oai:union.ndltd.org:uiowa.edu/oai:ir.uiowa.edu:etd-4927 |
| Date | 01 July 2013 |
| Creators | Niedzialomski, Amanda Jean |
| Contributors | Tomova, Maggy |
| Publisher | University of Iowa |
| Source Sets | University of Iowa |
| Language | English |
| Detected Language | English |
| Type | dissertation |
| Format | application/pdf |
| Source | Theses and Dissertations |
| Rights | Copyright 2013 Amanda Jean Niedzialomski |
Page generated in 0.0019 seconds