Optimal L(2,1)-labeling of Cartesian products of cycles, with an application to independent domination

摘要

The L(2,1)-labeling of a graph is an abstraction of the problem of assigning (integer) frequencies to radio transmitters, such that transmitters that are "close", receive different frequencies, and those that are "very close" receive frequencies that are further apart. The least span of frequencies in such a labeling is referred to as the /spl lambda/-number of the graph. Let n be odd /spl ges/5, k=(n-3)/2 and let m/sub 0/,...,m/sub k-1/, m/sub k/ each be a multiple of n. It is shown that /spl lambda/(Cm/sub 0//spl square//spl middot//spl middot//spl middot//spl square/Cm/sub k-1/) is equal to the theoretical minimum of n-1, where C/sub r/ denotes a cycle of length r and "/spl square/" denotes the Cartesian product of graphs. The scheme works for a vertex partition of Cm/sub 0//spl square//spl middot//spl middot//spl middot//spl square/Cm/sub k-1//spl square/Cm/sub k/ into smallest (independent) dominating sets.