The -conjecture for -labelings is true for total graphs

An L ( 2 , 1 ) -labeling of a graph G is defined as a function f from the vertex set V ( G ) into the nonnegative integers such that for any two vertices x , y , | 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 ) is the distance between x and y in G . The L ( 2 , 1 ) -labeling number λ 2 , 1 ( G ) of G is the smallest number k such that G has an L ( 2 , 1 ) -labeling with k = max { f ( x ) | x ∈ V ( G ) } . Griggs and Yeh conjectured that λ 2 , 1 ( G ) ≤ Δ 2 for any simple graph with maximum degree Δ ≥ 2 . In this paper, we consider the total graph T ( G ) of a graph G and derive its upper bound of λ 2 , 1 ( T ( G ) ) . Shao, Yeh and Zhang had proved that λ 2 , 1 ( T ( G ) ) ≤ max { 3 4 Δ 2 + 1 2 Δ , 1 2 Δ 2 + 2 Δ } . We improve the bound to 1 2 Δ 2 + Δ , which shows that the conjecture of Griggs and Yeh is true for the total graph. In addition, we obtain the exact value of λ 2 , 1 ( T ( K m , n ) ) for the total graph of a complete bipartite graph K m , n with m ≥ n ≥ 1 .