Group path covering and L(j,k)L(j,k)-labelings of diameter two graphs

L(j,k)L(j,k)-labeling is a kind of generalization of the classical graph coloring motivated from a kind of frequency assignment problem in radio networks, in which adjacent vertices are assigned integers that are at least j apart, while vertices that are at distance two are assigned integers that are at least k   apart. The span of an L(j,k)L(j,k)-labeling of a graph G   is the difference between the maximum and the minimum integers assigned to its vertices. The L(j,k)L(j,k)-labeling number of G  , denoted by λj,k(G)λj,k(G), is the minimum span over all L(j,k)L(j,k)-labelings of G. Georges, Mauro and Whittlesey (1994) [1] established the relationship between λ2,1(G)λ2,1(G) of a graph G   and the path covering number of GcGc (the complement of G). Georges, Mauro and Stein (2000) [2] determined the L(j,k)L(j,k)-labeling numbers of Cartesian products of two complete graphs. Lam, Lin and Wu (2007) [3] determined the λj,kλj,k-numbers of direct products of two complete graphs. In 2011, we (Wang and Lin, 2011 [4]) generalized the concept of the path covering to the t-group path covering of a graph where t  (⩾1)(⩾1) is an integer and established the relationship between the L′(d,1)L′(d,1)-labeling number (d⩾2)(d⩾2) of a graph G   and the (d−1)(d−1)-group path covering number of GcGc. In this paper, we establish the relationship between the λj,k(G)λj,k(G) of a graph G   with diameter 2 and the ⌊j/k⌋⌊j/k⌋-group path coverings of GcGc. Using those results, we can have shorter proofs to obtain the λj,kλj,k of the Cartesian products and direct products of complete graphs.

► Establish the relationship between λj,k(G)λj,k(G) of a graph G   with diameter 2 and the ⌊j/k⌋⌊j/k⌋-group path coverings of GcGc. ► Give shorter proofs to obtain the λj,kλj,k-numbers of KnKmKnKm, KnKnKnKn and Kn×KmKn×Km based on the above results. ► Determine the λj,kλj,k-number of Kk1,k2,…,kqKk1,k2,…,kq (the complete q-partite graph).