L(3,1)-labeling of circulant graphs.

An L (3 , 1) -labeling of a graph Γ is an assignment of non-negative integers to the vertices such that if two vertices u and v are adjacent then they receive labels that differ by at least 3 , and when u and v are not adjacent but there is a two-hop path between them, then they receive labels that differ by at least one. The span λ of such a labeling is the difference between the largest and the smallest vertex labels assigned. Let λ 3 1 (Γ) denote the least λ such that Γ admits an L (3 , 1) -labeling using labels from { 0 , 1 , ... , λ }. A Cayley graph of group G is called circulant graph of order n , if G = ℤ n . In this paper initially we investigate the L (3 , 1) -labeling for circulant graphs with "large" connection sets, and then we extend our observation and find the span of L (3 , 1) -labeling for any circulants of order n. [ABSTRACT FROM AUTHOR]