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

Given two non-negative 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 NP-complete, 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 asButterfly-like, 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.