On n-fold L(j, k)-and circular L(j, k)-labelings of graphs

We initiate research on the multiple distance 2 labeling of graphs in this paper. Let n, j, k be positive integers. An n-fold L(j, k)-labeling of a graph G is an assignment f of sets of nonnegative integers of order n to the vertices of G such that, for any two vertices u, v and any two integers a is an element of f (u), b is an element of f (v), vertical bar a - b vertical bar >= j if uu is an element of E(G), and vertical bar a - b vertical bar >= k if u and v are distance 2 apart. The span off is the absolute difference between the maximum and minimum integers used by f. The n-fold L(j. k)-labeling number of G is the minimum span over all n-fold L(j, k)-labelings of G. Let n, j, k and m be positive integers. An n-fold circular m-L( j, k)-labeling of a graph G is an assignment f of subsets of {0. 1 m 1} of order n to the vertices of G such that, for any two vertices u, v and any two integers a is an element of f (u), b is an element of f ( v), min{vertical bar a - b vertical bar, m - vertical bar a - b vertical bar >= j if uv is an element of E(G), and min{(vertical bar a-b vertical bar, m - vertical bar a - b vertical bar} >= k if u and v are distance 2 apart. The minimum m such that G has an n-fold circular m-L(j, k)-labeling is called the n-fold circular L(j, k)labeling number of G. We investigate the basic properties of n-fold L(j, k)-labelings and circular M. k)-labelings of graphs. The n-fold circular L(j. k)-labeling numbers of trees, and the hexagonal and p-dimensional square lattices are determined. The upper and lower bounds for the n-fold L(j. k)-labeling numbers of trees are obtained. In most cases, these bounds are attainable. In particular, when k = 1 both the lower and the upper bounds are sharp. In many cases, the n-fold L( j, k)-labeling numbers of the hexagonal and p-dimensional square lattices are determined. In other cases, upper and lower bounds are provided. In particular, we obtain the exact values of the n-fold L(j, 1)-labeling numbers of the hexagonal and p-dimensional square lattices. (C) 2012 Elsevier B.V. All rights reserved.