L(2; 1)-LABELING OF TRAPEZOID GRAPHS

L(2; 1)-LABELING OF TRAPEZOID GRAPHS

S. Paul, SK Amanathulla, M. Pal, A. Pal

[PDF]

Abstract

An L(2; 1)????labeling (L21L) of a graph G = (V;E) is an assignment f from the node-set V to the set f0; 1; 2; 3; : : :g so that adjoining nodes get numbers at least two apart, and nodes at distance two get di erent numbers. The L21L number  2;1(G) is the di erence between the greatest and least label used in the labeling process. In this paper, we have proved that, for a trapezoid graph (TG) G, the upper bound of  2;1(G)   5  ???? 4, where   is the maximum degree of the graph G. This paper also provides L21L of a simple triangle graph, a subclass of TG. We have shown that for a simple triangle graph, the upper bound of  2;1(G) is 4 .

Keywords

Frequency assignment, L(2,1)-labeling, trapezoid graphs.