Surjective L (2, 1)-labeling of cycles and circular-arc graphs
Sk Amanathulla, Madhumangal Pal · Journal of Intelligent & Fuzzy Systems · 2018
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.