A RESTRICTED L(2, 1)-LABELLING PROBLEM ON INTERVAL GRAPHS

A RESTRICTED L(2, 1)-LABELLING PROBLEM ON INTERVAL GRAPHS

N. Patra, SK Amanathulla, M. Pal, S. Mondal

[PDF]

Abstract

In a graph G = (V;E), L(2; 1)-labelling is considered by a function ` whose domain is V and codomain is set of non-negative integers with a condition that the vertices which are adjacent assign labels whose di erence is at least two and the ver- tices whose distance is two, assign distinct labels. The di erence between maximum and minimum labels among all possible labels is denoted by  2;1(G). This paper contains a variant of L(2; 1)-labelling problem. In L(2; 1)-labelling problem, all the vertices are L(2; 1)-labeled by least number of labels. In this paper, maximum allowable label K is given. The problem is: L(2; 1)-label the vertices of G by using the labels f0; 1; 2; : : : ;Kg such that maximum number of vertices get label. If K labels are adequate for labelling all the vertices of the graph then all vertices get label, otherwise some vertices remains unlabeled. An algorithm is designed to solve this problem. The algorithm is also illus- trated by examples. Also, an algorithm is designed to test whether an interval graph is no hole label or not for the purpose of L(2; 1)-labelling.

Keywords

Interval graph, graph labelling, L(2; 1)-labelling, holes in label.