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

An L (2, 1)-labeling of a graph G is a function f from the vertex set V (G) to the set of all nonnegative integers such that | f (x) - f (y) | ≥ 2 if d (x, y) = 1 and | f (x) - f (y) | ≥ 1 if d (x, y) = 2, where d (x, y) denotes the distance between x and y in G. The L (2, 1)-labeling number λ (G) of G is the smallest number k such that G has an L (2, 1)-labeling with max {f (v) : v ∈ V (G)} = k. Griggs and Yeh conjecture that λ (G) ≤ Δ2for any simple graph with maximum degree Δ ≥ 2. In this work, we consider the total graph and derive its upper bound of λ (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.