Radio Graceful Hamming Graphs

For $ k \in \mathbb{Z}_+ $ and $G$ a simple, connected graph, a $k$-radio labeling $ f : V (G) \rightarrow \mathbb{Z}_+ $ of $G$ requires all pairs of distinct vertices $u$ and $v$ to satisfy $ |f(u) − f(v)| \ge k + 1 − d(u, v) $. We consider $k$-radio labelings of $G$ when $ k = \text{diam} (G)$. In this setting, $f$ is injective; if $f$ is also surjective onto $ {1, 2, . . ., |V (G)|} $, then $f$ is a consecutive radio labeling. Graphs that can be labeled with such a labeling are called radio graceful. In this paper, we give two results on the existence of radio graceful Hamming graphs. The main result shows that the Cartesian product of $t$ copies of a complete graph is radio graceful for certain $t$. Graphs of this form provide infinitely many examples of radio graceful graphs of arbitrary diameter. We also show that these graphs are not radio graceful for large $t$.