Radio gracefulness of Moore graphs and beyond

Abstract

The study of radio graceful labelings is motivated by modeling efficient frequency assignment to radio towers, cellular towers, and satellite networks. For a simple, connected graph $G=(V(G),E(G))$, a radio labeling is a mapping $f:V(G)\to {\mathbb{Z}}^{+}$ satisfying (for any distinct vertices $u,v$) $$|f(u)-f(v)|+d(u,v)\ge diam(G)+1,$$ where $d(u,v)$ is the distance between $u$ and $v$ in $G$ and $diam(G)$ is the diameter of $G$. A graph is radio graceful if there is a radio labeling such that $f(V(G))=\{1,\dots ,|V(G)|\}$. In this paper, we determine the radio gracefulness of low-diameter graphs with connections to high-performance computing, including Moore graphs, bipartite Moore graphs, and approximate Moore graphs like $(r,g)-$cages, Erdős-Rényi polarity graphs, and McKay-Miller-Širáň graphs. We prove a new necessary and sufficient condition for radio graceful bipartite graphs with diameter $3$. We compute the radio number of $(r,g)-$cages arising from generalized $n-$gons. Additionally, we determine Erdős-Rényi polarity graphs and McKay-Miller-Širáň graphs are radio graceful.

17 pages, 3 figures