On the radio number of toroidal grids.

Abstract

A radio coloring of a simple connected graph G is a mapping f : V (G) → {0, 1, 2, . . .} such that |f(u)− f(v)| diam(G)+1−d(u, v) for each pair of distinct vertices u and v of G, where diam(G) is the diameter of G and d(u, v) is the distance between u and v in G. The span of a radio coloring f , span(f), is the number maxu∈V (G) f(u). The radio number of G, rn(G), is defined as minf{span(f) : f is a radio coloring of G}. In this paper, we determine the radio number of the toroidal grid Tm,n (the cartesian product of cycle Cm with the cycle Cn), when at least one of m and n is an even integer. Furthermore, a lower bound is given for the same when both m and n are odd integers.