کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949699 | 1440202 | 2017 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
L(2,1)-Labeling of Kneser graphs and coloring squares of Kneser graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: L(2,1)-Labeling of Kneser graphs and coloring squares of Kneser graphs L(2,1)-Labeling of Kneser graphs and coloring squares of Kneser graphs](/preview/png/4949699.png)
چکیده انگلیسی
The frequency assignment problem is to assign a frequency to each radio transmitter so that transmitters are assigned frequencies with allowed separations. Motivated by a variation of the frequency assignment problem, the L(2,1)-labeling problem was put forward. 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 a L(2,1)-labeling with max{f(v):vâV(G)}=k. Griggs and Yeh (1992) conjectured that λ(G)â¤Î2 for any graph with maximum degree Îâ¥2. The Kneser graph K(a,b) is defined as the graph whose vertices correspond to all b-subsets of the a-set A={1,2,â¦,a}, with edges joining pairs of vertices that correspond to non-overlapping b-subsets. The chromatic number of the Kneser graph K(a,b) is aâ2b+2. Füredi put forward an open problem: What is the value for the chromatic number of the square of any Kneser graph K(a,b) (the square of a graph is the graph obtained by adding edges joining vertices at distance 2)? In this article, the L(2,1)-labeling numbers of Kneser graphs K(a,b) are considered. The combined upper bounds for the L(2,1)-labeling numbers of Kneser graphs are derived by using two approaches. The exact L(2,1)-labeling number of Kneser graph K(a,b) for aâ¥3bâ1 is obtained, and it is proved that Griggs and Yeh's conjecture holds for Kneser graphs and the L(2,1)-labeling numbers of Kneser graphs are much better than Î2 in most cases. We also provide bounds for the chromatic number of the square of any Kneser graph K(a,b) using the proof for the upper bounds of the L(2,1)-labeling numbers of Kneser graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 221, 20 April 2017, Pages 106-114
Journal: Discrete Applied Mathematics - Volume 221, 20 April 2017, Pages 106-114
نویسندگان
Zhendong Shao, Igor Averbakh, Roberto Solis-Oba,