The L(2,1)L(2,1)-labeling on graphs and the frequency assignment problem

An L(2,1)L(2,1)-labeling of a graph GG is a function ff from the vertex set V(G)V(G) to the set of all nonnegative integers such that |f(x)−f(y)|≥2|f(x)−f(y)|≥2 if d(x,y)=1d(x,y)=1 and |f(x)−f(y)|≥1|f(x)−f(y)|≥1 if d(x,y)=2d(x,y)=2, where d(x,y)d(x,y) denotes the distance between xx and yy in GG. The L(2,1)L(2,1)-labeling number λ(G)λ(G) of GG is the smallest number kk such that GG has an L(2,1)L(2,1)-labeling with max{f(v):v∈V(G)}=kmax{f(v):v∈V(G)}=k. Griggs and Yeh conjecture that λ(G)≤Δ2λ(G)≤Δ2 for any simple graph with maximum degree Δ≥2Δ≥2. In this work, we consider the total graph and derive its upper bound of λ(G)λ(G). The total graph plays an important role in other graph coloring problems. Griggs and Yeh’s conjecture is true for the total graph in some cases.