Improved Bounds for Radio k-Chromatic Number of Hypercube Qn
Abstract
A number of graph coloring problems have their roots in a communication problem known as the channel assignment problem. The channel assignment problem is the problem of assigning channels (nonnegative integers) to the stations in an optimal way such that interference is avoided as reported by Hale (2005). Radio k-coloring of a graph is a special type of channel assignment problem. Kchikech et al. (2005) have given a lower and an upper bound for radio k-chromatic number of hypercube Qn, and an improvement of their lower bound was obtained by Kola and Panigrahi (2010). In this paper, we further improve Kola et al.′s lower bound as well as Kchikeck et al.′s upper bound. Also, our bounds agree for nearly antipodal number of Qn when n ≡ 2 (mod 4).
1. Introduction
Radio coloring is derived from the assignment of radio frequencies (channels) to a set of transmitters. The frequencies assigned depend on the geographical distance between the transmitters: the closer two transmitters are, the greater the potential for interference between their signals. Thus, when the distance between two transmitters is small, the difference in the frequencies assigned must be relatively large, whereas two transmitters at a large distance may be assigned relatively close frequencies.
Finding radio k-chromatic number of a graph is an interesting yet difficult combinatorial problem with potential applications to FM channel assignment. The concept of radio k-coloring was introduced by Chartrand et al. in [1]. But so far, radio k-chromatic number is known for very limited classes of graphs and for specific values of k only. Radio numbers of Cn and Pn [2], [3], and [4] are known. Recently, radio numbers of complete m-array trees have been found by Li et al. [5]. Radio number of hypercubes is determined by Khennoufa and Tongi [6] and Kola and Panigrahi [7] independently. Khennoufa et al. have also found antipodal number of Qn. For k = n − 1, n − 2, n − 3 and n − 4 the radio k-chromatic number of path Pn has been determined in [4, 8–10], respectively. Juan and liu [11] have determined the antipodal number of cycle Cn. Kchikech et al. [12] have given an upper and a lower bound for radio k-chromatic number of cartesian product of two graphs G and G′. Also, as a particular case, they have given an upper and a lower bounds for radio k-chromatic number of hypercube Qn, but these bounds were very loose. Recently, Kola and Panigrahi [7] have improved their lower bound for rck(Qn) and have shown that this bound is exact for radio number of Qn. In this paper, we obtain an improvement of Kola et al.′s lower bound as well as Kchikeck et al.′s upper bound. Further, we show that these bounds agree for rcn−2(Qn), n ≡ 2 (mod 4).
2. Improved Lower Bound
In this section, we give an improved lower bound of rck(Qn) for 2 ⩽ k ⩽ n − 2. For a hypercube Qn of dimension n, the vertex set can be taken as binary n-bit strings and two vertices being adjacent if the corresponding strings differ at exactly one bit.
Definition 2.1. For any two n-bit binary strings a = a0a1 ⋯ an−1 and b = b0b1 ⋯ bn−1, the Hamming distance dH(a, b) between a and b is the number of bits in which they differ. In particular, if x, y ∈ {0,1}, then dH(x, y) = 0 or 1 according as x = y or x ≠ y.
If u and v are two vertices of Qn with a and b as the corresponding strings, then . Two n-bit binary strings may differ in at most n positions, so diameter of Qn is n.
The results in the following lemma may be found in [7].
Lemma 2.2. For any three vertices x, y, and z of the hypercube Qn, the following holds:
- (i)
d(x, y) + d(y, z) + d(x, z) ⩽ 2n,
- (ii)
d(x, y) + d(y, z) + d(x, z) = 2n, if d(x, y) = n.
The following lower bound for rck(Qn) was determined by Kola and Panigrahi [7].
Theorem 2.3 (see [7].)For the hypercube Qn of dimension n⩾2 and for any positive integer k with 2 ⩽ k ⩽ n,
In the theorem below, we give an improvement of the above lower bound of rck(Qn) for all values of n and 2 ⩽ k ⩽ n − 2.
Theorem 2.4. For a hypercube Qn of dimension n⩾2 and for any positive integer k with 2 ⩽ k ⩽ n − 2,
Proof. Let f be any radio k-coloring of Qn and be an ordering of the vertices of Qn such that f(xj+1)⩾f(xj), 1 ⩽ j ⩽ 2n − 1. Obviously, f(x1) = 0 and . Since f is a radio k-coloring of Qn, for every i with 0 ⩽ i ⩽ 2n − 2, we have the following:
3. Improved Upper Bound
In this section, we give an improved upper bound of rck(Qn). For better presentation, we need the definition below.
Definition 3.1. For two positive integers n and l with l < n, a binary (n, l)-Gray code is a listing of all the n-bit binary strings such that the Hamming distance between two successive strings is exactly l. Further, a quasi (n, l)-Gray code is a listing of all the n-bit binary strings such that the Hamming distance between two successive strings is exactly l except between the two items 2n−1 − 1 and 2n−1 for which it is l − 1 or l + 1.
Notation 3.2. For any positive integer n, we define δ(n) as
The following theorem gives a partition of the vertex set of Qn that will be used to find the upper bound of rck(Qn).
Theorem 3.3. For a hypercube Qn of dimension n, there exists a partition of the vertex set of Qn with the partite sets U1 = {xi : i = 0,1, …, 2n−1 − 1} and U2 = {yi : i = 0,1, …, 2n−1 − 1} satisfying the followyng properties:
- (a)
d(xi, xi+1) = ⌊n/2⌋ = d(yi, yi+1), for all i = 0,1, …, 2n−1 − 2 except i = 2n−2 − 1,
- (b)
d(xi, xi+1) = ⌊n/2⌋ − δ(n) or ⌊n/2⌋ + δ(n), for i = 2n−2 − 1,
- (c)
d(yi, yi+1) = ⌊n/2⌋ − δ(n) or ⌊n/2⌋ + δ(n), for i = 2n−2 − 1,
- (d)
d(xi, yi) = n, for all i = 0,1, …, 2n−1 − 1,
Proof. Let and be two copies of Qn−1 induced by all the n-bit strings with starting bit 0 and 1, respectively. Let be the ordering of the vertices of which induce a quasi (n − 1, ⌊n/2⌋)-Gray code if n≢2 (mod 4) and a (n − 1, n/2)-Gray code if n ≡ 2 (mod 4); (such code exists, see [6]). We take , i = 1,2, …, 2n−1 − 1, that is, is obtained from xi by changing 0s to 1s and vice versa. Now, is an ordering of the vertices of which induces the same Gray code as in the above. By taking U1 = {xi : i = 0,1, …, 2n−1 − 1} and U2 = {yi : i = 0,1, …, 2n−1 − 1}, we get the result.
The following upper bound for rck(Qn) was determined by Kchikech et al. in [12].
Theorem 3.4 (see [12].)For the hypercube Qn of dimension n⩾2 and for any k⩾2,
The theorem below gives an improvement of this upper bound of rck(Qn).
Theorem 3.5. For the hypercube Qn of dimension n⩾2 and for any positive integer k, 2 ⩽ k ⩽ n − 2,
Proof. Here, we consider the same partition of V(Qn) as in Theorem 3.3. We first take 2⌊n/2⌋ − 2 ⩽ k ⩽ n − 2. For these values of k, we define a coloring f of V(Qn) with f(x0) = 0 and
Therefore, f is a radio k-coloring of Qn and the span of f is (2n−1 − 1)(k + 1 − ⌊n/2⌋) + δ(n). Next, we consider the value of k as ⌊n/2⌋ ⩽ k ⩽ 2⌊n/2⌋ − 3 and define a coloring f with f(x0) = 0, and
Finally, we take 2 ⩽ k ⩽ ⌊n/2⌋ − 2. From Theorem 2.4, we have d(xi, xi+1), d(xi, yi), d(xi, yi+1), d(xi+1, yi), d(yi, yi+1)⩾k + 1. So, we use the same color for the vertices xi, xi+1, yi and yi+1. In this case, we define a coloring f as f(xi) = (i/2)k = f(yi), f(xi+1) = f(xi), f(yi+1) = f(yi), i = 0,2, …, 2n−1 − 2. It is easy to show that f is a radio k-coloring of Qn with the span k2n−2 − k.
| u, v ∈ U1 ∪ U2 | Value of |i − j| | d(u, v) | k + 1 − d(u, v) | |f(u) − f(v)| |
|---|---|---|---|---|
| xi, xj ∈ U1, or yi, yj ∈ U2 | |i − j | = 1 | ⌊n/2⌋ | k + 1 − ⌊n/2⌋ | k + 1 − ⌊n/2⌋ |
| |i − j | ⩾2 | ⩾1 | ⩽k | ⩾k | |
| xi ∈ U1, yj ∈ U2 | i − j = 0 | n | ⩽0 | 0 |
| |i − j | = 1 | ⩾⌊n/2⌋ | ⩽k + 1 − ⌊n/2⌋ | ⩾k + 1 − ⌊n/2⌋ | |
| |i − j | ⩾2 | ⩾1 | ⩽k | ⩾k |
Observe that the bounds given in Theorems 2.4 and 3.5 agree for k = n − 2 with n ≡ 2 (mod 4). Therefore we have determined the nearly antipodal number of Qn which is given in the theorem below.
Theorem 3.6. For n ≡ 2 (mod 4), the nearly antipodal number rcn−2(Qn) of the hypercube Qn is (2n−1 − 1)(n − 2)/2.
