A General Approach to \it\bfseries L(h,k)Label Interconnection Networks

Abstract
Given two nonnegative integers h and k, an L(h,k)\em labelingof a graph G=(V,E) is a function from the setV to a set of colors, such that adjacent nodes take colors atdistance at least h, and nodes at distance 2 take colors atdistance at least k. The aim of the L(h,k)labeling problem isto minimize the greatest used color. Since the decisional versionof this problem is NPcomplete, it is important to investigateparticular classes of graphs for which the problem can beefficiently solved.It is well known that the most common interconnection topologies, such asButterflylike, Bene\vs, CCC, Trivalent Cayley networks, are allcharacterized by a similar structure: they have nodes organized as a matrix and connections are divided into layers.So we naturally introduce a new class of graphs,called (l \times n)\em multistage graphs, containing the most common interconnection topologies, on which we study the L(h,k)labeling.A general algorithm for L(h,k)labeling thesegraphs is presented, and from this method an efficientL(2,1)labeling for Butterfly and CCC networks is derived. Finally we describe a possible generalization of our approach.

