Radio numbers for generalized prism graphs

Abstract

A radio labeling is an assignment $c:V(G)\to \text{N}$ such that every distinct pair of vertices $u,v$ satisfies the inequality $d(u,v)+|c(u)-c(v)|\geq \diam(G)+1$. The span of a radio labeling is the maximum value. The radio number of $G$, $rn(G)$, is the minimum span over all radio labelings of $G$. Generalized prism graphs, denoted $Z_{n,s}$, $s\ge 1$, $n\ge s$, have vertex set $\{(i,j)|i=1,2\text{and}j=1,...,n\}$ and edge set $\{((i,j),(i,j\pm 1))\}\cup \{((1,i),(2,i+\sigma ))|\sigma =-\lfloor \frac{s-1}{2}\rfloor \dots ,0,\dots ,\lfloor \frac{s}{2}\rfloor \}$. In this paper we determine the radio number of $Z_{n,s}$ for $s=1,2$ and $3$. In the process we develop techniques that are likely to be of use in determining radio numbers of other families of graphs.

To appear in Discussiones Mathematicae Graph Theory. 16 pages, 1 figure