L(3,2,1)-Labeling problems on trapezoid graphs

In graph theory, one of the most important problems is graph labeling. Labeling of graph has a very wide range of applications in x-ray crystallography, missile guidance, coding theory, signal processing, radar, data base management, astronomy, communication network addressing, circuit design, etc. An extension of L(2, 1)-labeling (L21-labeling) is L(3, 2, 1)-labeling (L321-labeling), which is now becoming a well-studied problem due to its application in real life situations. L21-labeling problem and the importance of L321-labeling problem motivates us to consider L321-labeling problem for trapezoid graph. The L321-labeling of a graph G = (V,E) is an assignment zeta from V to the set {0, 1, 2, horizontal ellipsis } such that if d(p(1), p(2)) = 1 then |zeta(p(1)) - zeta(p(2))| >= 3, if d(p(1),p(2)) = 2 then |zeta(p(1)) - zeta(p(2))| >= 2 and if d(p(1),p(2)) = 3 then |zeta(p(1)) - zeta(p(2))|>= 1, where d(p(1),p(2)) is the distance between the nodes p(1) and p(2). The L321-labeling number of a graph is denoted by lambda 3,2,1(G), it is the highest label used to label the graph G. In this paper, for trapezoid graph G, it is proved that lambda(3,2,1)(G) <= max{11 Delta - 8, 13 Delta - 18}, where Delta is the degree of the graph G. This upper bound is the first upper bound for L321-labeling problem on trapezoid graph. Also, to label any trapezoid graph, we have designed an algorithm which maintains the upper bound of the label.