The L(2, 1)-Labeling And Algorithm Of Graphs

The L(2, 1)-labeling of graphs arises from a variation frequency assignment problem by Hale. Let Z be a set of non-negative integers, An k-L(2, l)-labeling of G is a functionφ:V(G)→Z, such that, for any two vertices x,y∈V(G),|φ(x)-φ(y)|≥2 ifd_G(x, y) = 1; and |φ(x)-φ(y)|≥1 if d_G(x, y) = 2. The L(2, 1)-labeling number of G, denoted byλ(G), is the smallest number k such that G has an k-L(2, 1)-labeling.For any graph G with maximum degree△(G), Griggs and Yeh conjectured thatλ(G)≤△~2(G). In recent years, students do a lot of work to prove that conjecture, however, the new bound isλ(G)≤△~2(G)+△(G)-2. Now, the most study is to confirm the conjecture for some classes of graphs.In this thesis, we firstly summarize the main results and evolution on the L(2,1)-labeling in recent years, then we investigate some graphs:(1) We explore the L(2,1)-labeling of cacti, and prove thatλ(G)≤△(G)+2 when△(G)≥5. We present several conditions forλ(G)≤△(G)+2 when△(G) = 3,4, and illustrate some cacti forλ(G)=△(G)+3when△(G) = 3,4.The L(2, 1)-labeling of L(G) is analogous to the L(2, 1)-edge-labeling of G. We usually denoted byλ'(G) the L(2,1)-edge-labeling number. According to the algorithm, we explore the L(2,1)-edge-labeling problem of two classes of graphs.(2) For a graph G with△(G) = 3, we present a linear time algorithm to 16-L(2,1)-edge-labeling the graph G. So we prove thatλ'(G)≤16 and show that the conjecture of Griggs and Yeh is confirmed for the line graph of G with△(G) = 3.(3) For a subcubic graph G with△(G) =△(L(G)) = 3, we present a linear time algorithm to 9-L(2,1)-edge-labeling the graph G. So we prove thatλ'(G)≤9 and show that the conjecture of Griggs and Yeh is confirmed for the line graph of G with △(G) =△(L(G)) = 3.