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

Abstract

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 Δ > 2 can be surjectively labeled using L (2, 1)-labeling if n = 4Δ - 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.