Authors : S.K. Amanathulla and Madhumangal Pal
Abstract: An L(0, 1)-labeling of a graph G = (V, E) is a function f from the vertex set V(G) to the set of non-negative integers such that /f(x)-f(y)/≥0 if d(x, y) = 1 and /f(x)-f(y)/≥1 if d(x, y) = 2. The L(0, 1)-labeling number of a graph G, denoted by λ0, 1 (G) is the difference between highest and lowest labels used. Similarly, L(1, 1)-labeling of a graph G = (V, E) is a function f from its vertex set V to the set of non-negative integers such that /f(x)-f(y)/≥1 if d(x, y) = 1 or 2. The span of an L(1, 1)-labeling f of G is max{f(v): v∈V}. The L(1, 1)-labeling number λ1, 1 (G) of G is the smallest non-negative integer k such that G has a L(1, 1)-labeling of span k. In this study, for any circular-arc graph G, we have shown that λ0, 1(G)≤Δ and λ1, 1(G)≤2 where Δ represents the degree of the graph G. Also two algorithms are designed to label a circular-arc graph by maintaining L(0, 1)-and L(1, 1)-labeling conditions. The running time of these algorithms are O(nΔ2) and O(nΔ), respectively where n represent the number of vertices of G.
S.K. Amanathulla and Madhumangal Pal, 2016. L(0,1) and L(1,1) Labeling Problems on Circular-Arc Graphs. International Journal of Soft Computing, 11: 343-350.