Relationships between distance two labellings and circular distance two labellings by group path covering

摘要

For the positive integers j and k with j >= k, L(j, k)-labelling is a kind of generalization of the classical graph coloring 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) -labelling of a graph G is the difference between the maximum and the minimum integers assigned to its vertices. The L(j,-k)-labelling number of G, denoted by lambda(j,k) (G), is the minimum span over all L(j, k)-labellings of G. An m-(j,k)-circular labelling of a graph G is a function f : V (G) -> {0, 1, ... , m-1} such that vertical bar f (u) - f(v)vertical bar(m) >= j if u and v are adjacent; and vertical bar f (u) - f (v)vertical bar(m) >= k if u and v are at distance two, where vertical bar x vertical bar(m) = min{vertical bar x vertical bar, m - vertical bar x vertical bar}. The span of an m -(j, k) -circular labelling of a graph G is the difference between the maximum and the minimum integers assigned to its vertices. The m -(j, k) -circular labelling number of G, denoted by sigma(j,k) (G), is the minimum span over all m-(j, k)-circular labelling of G. The L' (j, k) -labelling, is a one-to-one L(j, k) -labelling and the m-(j,k)'-circular labelling is a one-to-one m -(j, k) -circular labelling. Denoted by lambda(j)',(k) (G) the L' (j, k) -labelling number and sigma(j)'(,k) (G) the m -(j, k)'-circular labelling number. When j = d, k = 1, L(j, k) labelling becomes L(d, 1) -labelling. The other labellings are similar. [Discrete Math. 232 (2001) 163-169] determined the relationship between lambda(2,1) (G) and sigma(2,1)(G) for a graph G. We generalized the concept of the path covering to the t-group path covering (Inform Process Lett(2011)) of a graph. In this paper, using the t-group path covering, we establish some relationships between lambda'(d,1) (G) and sigma'(d,1)(G) and some relationships between lambda(j,k)(G) and sigma(j,k)(G) of a graph G with diameter 2. Using those results, we can have shorter proofs to obtain the sigma(j,k)-number of Cartesian products of complete graphs [J Comb Optim (2007) 14: 219-227].