Group path covering and distance two labeling of graphs

For a positive integer d  , an L(d,1)L(d,1)-labeling f of a graph G is an assignment of integers to the vertices of G   such that |f(u)−f(v)|⩾d|f(u)−f(v)|⩾d if uv∈E(G)uv∈E(G), and |f(u)−f(v)|⩾1|f(u)−f(v)|⩾1 if u and u are at distance two. The span   of an L(d,1)L(d,1)-labeling f of a graph is the absolute difference between the maximum and minimum integers used by f  . The L(d,1)L(d,1)-labeling number of G  , denoted by λd,1(G)λd,1(G), is the minimum span over all L(d,1)L(d,1)-labelings of G  . An L′(d,1)L′(d,1)-labeling of a graph G   is an L(d,1)L(d,1)-labeling of G   which assigns different labels to different vertices. Denote by λd,1′(G) the L′(d,1)L′(d,1)-labeling number of G  . Georges et al. [Discrete Math. 135 (1994) 103–111] established relationship between the L(2,1)L(2,1)-labeling number of a graph G   and the path covering number of GcGc, the complement of G. In this paper we first generalize the concept of the path covering of a graph to the t  -group path covering. Then we establish the relationship between the L′(d,1)L′(d,1)-labeling number of a graph G   and the (d−1)(d−1)-group path covering number of GcGc. Using this result, we prove that λ2,1′(G) and λ3,1′(G) for bipartite graphs G can be computed in polynomial time.

► A new graph parameter called the group path covering number is introduced. ► We establish the relationship between this parameter and distance two labeling number. ► This generalizes a well-known result about path covering and distance two labeling. ► Two special problems of distance two labeling are proved to be polynomially solvable.