On the complexity of exact algorithm for L (2, 1)-labeling of graphs

L(2,1)L(2,1)-labeling is a graph coloring model inspired by a frequency assignment in telecommunication. It asks for such a labeling of vertices with nonnegative integers that adjacent vertices get labels that differ by at least 2 and vertices in distance 2 get different labels. It is known that for any k   ⩾ 4 it is NP-complete to determine if a graph has a L(2,1)L(2,1)-labeling with no label greater than k.In this paper we present a new bound on complexity of an algorithm for finding an optimal L(2,1)L(2,1)-labeling (i.e. an L(2,1)L(2,1)-labeling in which the largest label is the least possible). We improve the upper complexity bound of the algorithm from O⁎(3.5616n)O⁎(3.5616n) to O⁎(3.2361n)O⁎(3.2361n). Moreover, we establish a lower complexity bound of the presented algorithm, which is Ω⁎(3.0739n)Ω⁎(3.0739n).

► The bound for the number of k  -element 2-packings in a connected graph. ► An exact algorithm for L(2,1)L(2,1)-labeling of graphs. ► New upper and lower bounds for the complexity of this algorithm.