An improved lower bound for the radio k k -chromatic number of the hypercube Qn Q n
For any simple connected graph G G with diameter d d and an integer k k , 1?k?d 1 ? k ? d , a radio k k -coloring  is an assignment f f of positive integers to the vertices of G G such that |f(u)?f(v)|?1+k?d(u,v) | f ( u ) ? f ( v ) | ? 1 + k ? d ( u , v ) , where u u and v v are any two distinct vertices of G G and d(u,v) d ( u , v ) is the distance between u u and v v . The maximum color (positive integer) assigned by f f to some vertex of G G is called the span  of f f . The minimum of spans of all possible radio k k -colorings of G G is called the radio k k -chromatic number  of G G , denoted by rc k ( G ) . For k=d k = d , the coloring is called the radio coloring  and the radio d d -chromatic number is the radio number  of G G . Kchikech etal. (2008) [3] have given upper and lower bounds for the radio k k -chromatic number of the hypercube Qn Q n for n?2 n ? 2 . In this paper, we give an improved lower bound and prove that the bound is sharp for radio coloring.
span radio k k -coloring k k k k k radio k k -chromatic number k k k k k