کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1708280 | 1012820 | 2011 | 4 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: The Δ2Δ2-conjecture for L(2,1)L(2,1)-labelings is true for total graphs The Δ2Δ2-conjecture for L(2,1)L(2,1)-labelings is true for total graphs](/preview/png/1708280.png)
An L(2,1)L(2,1)-labeling of a graph GG is defined as a function ff from the vertex set V(G)V(G) into the nonnegative integers such that for any two vertices xx, yy, |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) is the distance between xx and yy in GG. The L(2,1)L(2,1)-labeling number λ2,1(G)λ2,1(G) of GG is the smallest number kk such that GG has an L(2,1)L(2,1)-labeling with k=max{f(x)|x∈V(G)}k=max{f(x)|x∈V(G)}. Griggs and Yeh conjectured that λ2,1(G)≤Δ2λ2,1(G)≤Δ2 for any simple graph with maximum degree Δ≥2Δ≥2. In this paper, we consider the total graph T(G)T(G) of a graph GG and derive its upper bound of λ2,1(T(G))λ2,1(T(G)). Shao, Yeh and Zhang had proved that λ2,1(T(G))≤max{34Δ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))λ2,1(T(Km,n)) for the total graph of a complete bipartite graph Km,nKm,n with m≥n≥1m≥n≥1.
Journal: Applied Mathematics Letters - Volume 24, Issue 9, September 2011, Pages 1491–1494