L(2,1)-LABELING OF CIRCULANT GRAPHS

An L(2, 1)-labeling of a graph Gamma is an assignment of non-negative integers to the vertices such that adjacent vertices receive labels that differ by at least 2, and those at a distance of two receive labels that differ by at least one. Let lambda(1)(2)(Gamma) denote the least A such that Gamma admits an L(2, 1)-labeling using labels from {0, 1, ... , lambda}. A Cayley graph of group G is called a circulant graph of order n, if G = Z(n). In this paper initially we investigate the upper bound for the span of the L(2, 1)-labeling for Cayley graphs on cyclic groups with "large" connection sets. Then we extend our observation and find the span of L(2, 1)-labeling for any circulants of order n.