@article{MAKHILLIJSC201611621374,
title = {L(0,1) and L(1,1) Labeling Problems on Circular-Arc Graphs},
journal = {International Journal of Soft Computing},
volume = {11},
number = {6},
pages = {343-350},
year = {2016},
issn = {1816-9503},
doi = {ijscomp.2016.343.350},
url = {https://makhillpublications.co/view-article.php?issn=1816-9503&doi=ijscomp.2016.343.350},
author = {Madhumangal and},
keywords = {Frequency assignment,L(0, 1)-labeling,L(1, 1)-labeling,circular-arc,graph,span},
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.}
}