کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420320 | 683921 | 2006 | 6 صفحه PDF | دانلود رایگان |
An L(2,1)L(2,1)-labelling of a graph G is an assignment of nonnegative integers to the vertices of G such that adjacent vertices have numbers at least 2 apart, and vertices at distance 2 have distinct numbers. The L(2,1)L(2,1)-labelling number λ(G)λ(G) of G is the minimum range of labels over all such labellings. It was shown by Griggs and Yeh [Labelling graphs with a condition at distance 2, SIAM J. Discrete Math. 5 (1992) 586–595] that every tree T has Δ+1⩽λ(T)⩽Δ+2Δ+1⩽λ(T)⩽Δ+2. This paper provides a sufficient condition for λ(T)=Δ+1λ(T)=Δ+1. Namely, we prove that if a tree T contains no two vertices of maximum degree at distance either 1, 2, or 4, then λ(T)=Δ+1λ(T)=Δ+1. Examples of trees T with two vertices of maximum degree at distance 4 such that λ(T)=Δ+2λ(T)=Δ+2 are constructed.
Journal: Discrete Applied Mathematics - Volume 154, Issue 3, 1 March 2006, Pages 598–603