Distance three labellings for K-n x K-2

Abstract

In a wireless communication network, the channel assignment problem addresses the correct assignment of a frequency to each transmitter in the network. To avoid interference between two nearby transmitters, the assigned frequencies must satisfy certain conditions related to the distance between transmitters. We can use only a limited number of channels; hence, we have to minimize the range of frequencies used. The distance labelling of a graph is a mathematical model of the channel assignment problem derived from the work of Hale [Frequency assignment: Theory and application, Proc. IEEE 68 (1980), pp. 1497-1514]. Lam et al. [L(j, k)-labelings for the products of complete graphs, J. Comb. Optim. 14 (2007), pp. 219-227] addressed distance two labelling for the direct product K(n)xK(m) of complete graphs K-n and K-m. In this paper, we solve the distance three labelling problem for K(n)xK(2).