The Δ~2-conjecture for L(2,1)-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=maxf(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)) ≤max34Δ~2+12Δ,12Δ~2+2Δ. We improve the bound to 12Δ~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(Km,_n)) for the total graph of a complete bipartite graph Km,_n with m≥n≥1.