# Improved Bounds for Radiok-Chromatic Number of Hypercube Qn

Authors: Laxman Saha; Pratima Panigrahi; Pawan Kumar
Journal: International Journal of Mathematics and Mathematical Sciences
 (2011)

---

## 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). Radiok-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).


---

## Body

## 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.Radiok-coloring of a graph is a variation of the channel assignment problem. For a simple connected graph G of order n and diameter q, and a positive integer k with 1⩽k⩽q, a radiok-coloringf of G is an assignment of non-negative integers to the vertices of G such that for every two distinct vertices u and v of G(1.1)|f(u)-f(v)|⩾k+1-d(u,v),
where d(u,v) is the distance between u and v in G. The span of a radio k-coloring f, spank(f), is the maximum integer assigned to a vertex of G. The radiok-chromatic number of G, denoted by rck(G), is defined by rck(G)=min{spank(f):fisaradiok-coloringofG}. Since rc1(G) is the chromatic number χ(G), radio k-colorings are a generalization of ordinary vertex coloring of graphs. In the literature, rcq(G) is termed as radio number of G whereas rcq-1(G) and rcq-2(G) are called antipodal and nearly antipodal number of G, respectively. Since the problem is to find a radio k-coloring with minimum span, we use the least color 0 in every radio k-coloring appearing in this paper.Finding radiok-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], Cn2 [3], and Pn2 [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(mod4).


## 2. Improved Lower Bound

In this section, we give an improved lower bound ofrck(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 twon-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.Ifu and v are two vertices of Qn with a and b as the corresponding strings, then dQn(u,v)=dH(a,b). 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 verticesx,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 forrck(Qn) was determined by Kola and Panigrahi  [7].Theorem 2.3 (see [7]).
For the hypercubeQn of dimension n⩾2 and for any positive integer k with 2⩽k⩽n,
(2.1)rck(Qn)⩾{(3(k+1)-2n2)2n-1-k+12,ifkisodd,(3(k+1)-2n+12)2n-1-k+22,ifkiseven.In the theorem below, we give an improvement of the above lower bound ofrck(Qn) for all values of n and 2⩽k⩽n-2.Theorem 2.4.
For a hypercubeQn of dimension n⩾2 and for any positive integer k with 2⩽k⩽n-2,
(2.2)rck(Qn)⩾⌈3(k+1)-2n2⌉(2n-1-1).Proof.
Letf be any radio k-coloring of Qn and x1,x2,…,x2n be an ordering of the vertices of Qn such that f(xj+1)⩾f(xj), 1⩽j⩽2n-1. Obviously, f(x1)=0 and span(f)=f(x2n). Since f is a radio k-coloring of Qn, for every i with 0⩽i⩽2n-2, we have the following:
(2.3)f(xi+1)-f(xi)⩾k+1-d(xi+1,xi),f(xi+2)-f(xi+1)⩾k+1-d(xi+2,xi+1),f(xi+2)-f(xi)⩾k+1-d(xi+2,xi).
Adding (2.3) we get,
(2.4)2(f(xi+2)-f(xi))⩾3(k+1)-(d(xi,xi+1)+d(xi+2,xi+1)+d(xi+2,xi))⩾3(k+1)-2n(From(i)ofLemma2.2).
From the above inequality, we have f(xi+2)-f(xi)⩾⌈(3(k+1)-2n)/2⌉,foralli=1,3,…,2n-3 and summing up these we get, f(x2n-1)⩾⌈(3(k+1)-2n)/2⌉(2n-1-1). From this inequality and the fact that f(x2n)⩾f(x2n-1), we get the result.


## 3. Improved Upper Bound

In this section, we give an improved upper bound ofrck(Qn). For better presentation, we need the definition below.Definition 3.1.
For two positive integersn 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 integern, we define δ(n) as
(3.1)δ(n)={0,ifn≡2(mod⁡4),1,ifn≢2(mod⁡4).The following theorem gives a partition of the vertex set ofQn that will be used to find the upper bound of rck(Qn).Theorem 3.3.
For a hypercubeQn 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, where δ(n) is defined as in Notation 3.2.Proof.
LetQn-1′ and Qn-1′′ be two copies of Qn-1 induced by all the n-bit strings with starting bit 0 and 1, respectively. Let x0,x1,…,x2n-1-1 be the ordering of the vertices of Qn-1′ which induce a quasi (n-1,⌊n/2⌋)-Gray code if n≢2(mod4) and a (n-1,n/2)-Gray code if n≡2(mod4); (such code exists, see [6]). We take yi=x¯i, i=1,2,…,2n-1-1, that is, x¯i is obtained from xi by changing 0s to 1s and vice versa. Now, y0,y1,…,y2n-1-1 is an ordering of the vertices of Qn-1′′ 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 forrck(Qn) was determined by Kchikech et al. in [12].Theorem 3.4 (see [12]).
For the hypercubeQn of dimension n⩾2 and for any k⩾2,
(3.2)rck(Qn)⩽(2n-1)k-2n-1+1.The theorem below gives an improvement of this upper bound ofrck(Qn).Theorem 3.5.
For the hypercubeQn of dimension n⩾2 and for any positive integer k, 2⩽k⩽n-2,
(3.3)rck(Qn)⩽{(2n-1-1)(k+1-⌊n2⌋)+δ(n),if2⌊n2⌋-2⩽k⩽n-2,k2n-2-⌈k2⌉+δ(n),if⌊n2⌋-1⩽k⩽2⌊n2⌋-3,k2n-2-k,if2⩽k⩽⌊n2⌋-2,
where δ(n) is defined as in Notation 3.2.Proof.
Here, we consider the same partition ofV(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
(3.4)f(xi)=f(xi-1)+k+1-⌊n2⌋,i=1,2,…,2n-1-1,excepti=2n-2,f(x2n-2)=f(x2n-2-1)+k+1-⌊n2⌋+δ(n),f(yi)=f(xi),i=0,1,2,…,2n-1-1.
We first check the radio condition for the vertex x2n-2 with all other vertices. Let v∈V(Qn)-{x2n-2}. From the definition of f, |f(x2n-2)-f(u)|⩾k, except v∈{x2n-2-1,y2n-2-1,y2n-2,x2n-2+1,y2n-2+1}. From Theorem 3.3(b) and Lemma 2.2(ii), we have d(x2n-2-1,x2n-2),d(y2n-2-1,x2n-2)⩾⌊n/2⌋-δ(n) and therefore f(x2n-2)-f(v)=k+1+δ(n)-⌊n/2⌋⩾k+1-d(x2n-2,v), for v=x2n-2-1 or y2n-2-1. Similarly, for v=x2n-2+1 or y2n-2-1, we show f(x2n-2)-f(u)⩾k+1-d(x2n-2,u). Since f(x2n-2)=f(y2n-2) and d(x2n-2,y2n-2)=n, radio condition is trivially true for the pair (x2n-2,y2n-2). In a similar manner one can show that |f(y2n-2)-f(v)|⩾k+1-d(y2n-2,v), for all v∈V(Qn)-{y2n-2}. For the rest of the pairs of vertices in V(Qn), checking radio condition is straightforward from the definition of f. However, in Table 1, we compute the values of |f(u)-f(v)| and k+1-d(u,v) for every pair of vertices u,v∈V(Qn)-{x2n-2,y2n-2}.
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
(3.5)f(xi+1)=f(xi)+⌊k2⌋,ifiisevenandi≠2n-2-1,f(xi+1)=f(xi)+⌈k2⌉,ifiisodd,f(xi+1)=f(xi)+⌊k2⌋+δ(n),i=2n-2-1,f(yi)=f(xi),i=0,1,2,…,2n-1-1.
By a similar way as in the above, one can check that f is a radio k-coloring of Qn with the span f(x2n-1-1)=2n-2⌊k/2⌋+(2n-2-1)⌈k/2⌉+δ(n)=k2n-2-⌈k/2⌉+δ(n).
Finally, we take2⩽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.Table 1u,v∈U1∪U2Value 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⩾kxi∈U1,yj∈U2i-j=0n⩽00|i-j|=1⩾⌊n/2⌋⩽k+1-⌊n/2⌋⩾k+1-⌊n/2⌋|i-j|⩾2⩾1⩽k⩾kObserve that the bounds given in Theorems2.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.
Forn≡2(mod4), the nearly antipodal number rcn-2(Qn) of the hypercube Qn is (2n-1-1)(n-2)/2.


## 4. Concluding Remarks

Improved lower and upper bounds ofrck(Qn) have been obtained in Theorems 2.4 and 3.5, respectively. It is easy to verify that the bound given in Theorem 3.5 is an improvement over the bound in Theorem 3.4. However, below, we check that lower bound given in Theorem 2.4 is really an improvement over the bound in Theorem 2.3. From Theorem 2.4, we have(4.1)rck(Qn)⩾{(3(k+1)-2n2)(2n-1-1),ifkisodd,(3(k+1)-2n+12)(2n-1-1),ifkiseven,={(3(k+1)-2n2)2n-1+n-3(k+1)2,ifkisodd,(3(k+1)-2n+12)2n-1+n-3k+42,ifkiseven.
For odd integer k, (4.2)[(3(k+1)-2n2)2n-1+n-3(k+1)2]-[(3(k+1)-2n2)2n-1-k+12]=n-k-1⩾1,if2⩽k⩽n-2.
Again, if k is an even integer, then (4.3)[(3(k+1)-2n+12)2n-1+n-3k+42]-[(3(k+1)-2n+12)2n-1-k+22]=n-k-1⩾1,if2⩽k⩽n-2.
Theorem 3.6 gives the nearly antipodal number of Qn for n≡2(mod4). From Theorems 2.4 and 3.5, one gets that the difference between the lower and upper bound of rcn-2(Qn), n≡0 (mod 4), is equal to one, that is, (2n-1-1)(n-2)/2⩽rcn-2(Qn)⩽(2n-1-1)(n-2)/2+1.



---

*Source: 961649-2011-04-12.xml*