Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4949699 | Discrete Applied Mathematics | 2017 | 9 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Zhendong Shao, Igor Averbakh, Roberto Solis-Oba,