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.