Surjective L(2,1)-labeling of cycles and circular-arc graphs

L(2, 1)-labeling problem is a well studied problem due to its wide applications, specially in frequency assignment in (mobile) communication system, coding theory, X-ray crystallography, radar, circuit design, etc. Surjective L(2, 1)-labeling problem has now become a well studied problem. Motivated from the L(2, 1)-labeling problem and the importance of surjective L(2, 1)-labeling problem, we consider surjective L(2, 1)-labeling problems for cycles and circular-arc graphs. A surjective L(2, 1)-labeling of a graph G = (V, E) is a function f : V -> {1, 2, . . . , n} such that |f(x) - f(y)| >= 2 if d(x, y) = 1 and |f(x) - f(y)| >= 1 if d(x, y) = 2, and every label 1, 2, . . . , n is used exactly once, where d(x, y) represents the distance between the vertices x and y and n is the number of vertices of the graph G. In this paper, it is shown that any cycle C-n of length n can be surjectively L(2, 1)-labeled if n >= 5 and any circular-arc graph G with n vertices and degree Delta > 2 can be surjectively labeled using L(2, 1)-labeling if n = 4 Delta - 2. Also a polynomial time algorithm is designed to label a circular-arc graph by surjective L(2, 1)-labeling. This is the first result for the problems on both cycles and circular-arc graphs.