TY - JOUR
T1 - L(0,1) and L(1,1) Labeling Problems on Circular-Arc Graphs
AU - Pal, Madhumangal AU - Amanathulla, S.K.
JO - International Journal of Soft Computing
VL - 11
IS - 6
SP - 343
EP - 350
PY - 2016
DA - 2001/08/19
SN - 1816-9503
DO - ijscomp.2016.343.350
UR - https://makhillpublications.co/view-article.php?doi=ijscomp.2016.343.350
KW - Frequency assignment
KW -L(0
KW - 1)-labeling
KW -L(1
KW - 1)-labeling
KW -circular-arc
KW -graph
KW -span
AB - 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.
ER -