L(2, 1)-Labeling of Circulant Graphs

Abstract

An L(2, 1)-labeling of a graph Γ 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 λ12(Γ) denote the least λ such that Γ admits an L(2, 1)-labeling using labels from {0, 1, . . . , λ}. A Cayley graph of group G is called a circulant graph of order n, if G = Zn. 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.

Keywords

• graph coloring
• l(2
• 1)-labeling
• circulants
• 05c78