L(2,1,1)-Labeling of Circular-Arc Graphs

Abstract

Graph labeling problem has been broadly studied in recent past for its wide applications, in mobile communication system for frequency assignment, radar, circuit design, X-ray crystallography, coding theory, etc. An L211-labeling  (L211L) of a graph G = (V, E) is a function γ : V → Z^∗ such that |γ(u) − γ(v)| ≥ 2, if d(u, v) = 1 and |γ(u) − γ(v)| ≥ 1, if  d(u, v) = 1 or 2, where  Z^∗  be the set of non-negative integers and d(u, v) represents the distance between the nodes u and v. The L211L numbers of a graph G, are denoted by λ_2,1,1(G) which is the difference between largest and smallest labels used in L211L. In this article, for circular-arc graph (CAG) G we have proved that λ_2,1,1(G) ≤ 6∆ − 4, where ∆ represents the degree of the graph. Beside this we have designed a polynomial time algorithm to label a CAG satisfying the conditions of L211L. The time complexity of the algorithm is O(n∆²), where n is the number of nodes of the graph G.