Discussiones Mathematicae Graph Theory 28(1) (2008)
165178
doi: 10.7151/dmgt.1399
Mustapha Kchikech, Riadh Khennoufa and Olivier Togni
LE2I, UMR CNRS 5158
Université de Bourgogne, 21078 Dijon cedex, France
email: {kchikech, khennoufa, otogni}@ubourgogne.fr

for any two vertices x and y, where d_{G}(x,y) is the distance between x and y in G. The radio kchromatic number is the minimum of max{f(x)−f(y):x,y ∈ V(G)} over all radio klabelings f of G. In this paper we present the radio klabeling for the Cartesian product of two graphs, providing upper bounds on the radio kchromatic number for this product. These results help to determine upper and lower bounds for radio kchromatic numbers of hypercubes and grids. In particular, we show that the ratio of upper and lower bounds of the radio number and the radio antipodal number of the square grid is asymptotically [3/2].
Keywords: graph theory, radio channel assignment, radio klabeling, Cartesian product, radio number, antipodal number.
2000 Mathematics Subject Classification: 05C15, 05C78.
[1]  G. Chartrand, D. Erwin and P. Zhang, Radio antipodal colorings of cycles, Congr. Numer. 144 (2000) 129141. 
[2]  G. Chartrand, D. Erwin and P. Zhang, Radio antipodal colorings of graphs, Math. Bohem. 127 (2002) 5769. 
[3]  G. Chartrand, L. Nebeský and P. Zhang, Radio kcolorings of paths, Discuss. Math. Graph Theory 24 (2004) 521, doi: 10.7151/dmgt.1209. 
[4]  G. Fertin, E. Godard and A. Raspaud, Acyclic and kdistance coloring of the grid, Inform. Process. Lett. 87 (2003) 5158, doi: 10.1016/S00200190(03)002321. 
[5]  W. Imrich and S. Klavžar, Product graphs, Structure and recognition, With a foreword by Peter Winkler, WileyInterscience Series in Discrete Mathematics and Optimization (WileyInterscience, New York, 2000). 
[6]  M. Kchikech, R. Khennoufa and O. Togni, Linear and cyclic radio klabelings of trees, Discuss. Math. Graph Theory 27 (2007) 105123, doi: 10.7151/dmgt.1348. 
[7]  R. Khennoufa and O. Togni, A note on radio antipodal colourings of paths, Math. Bohemica 130 (2005) 277282. 
[8]  R. Khennoufa and O. Togni, The Radio Antipodal Number of the Hypercube, submitted, 2007. 
[9]  D. Král, L.D. Tong and X. Zhu, Upper Hamiltonian numbers and Hamiltonian spectra of graphs, Australasian J. Combin. 35 (2006) 329340. 
[10]  D. Liu, Radio Number for Trees, manuscript, 2006. 
[11]  D. Liu and M. Xie, Radio Number for Square Paths, Discrete Math., to appear. 
[12]  D. Liu and X. Zhu, Multilevel distance labelings for paths and cycles, SIAM J. Discrete Math. 19 (2005) 610621, doi: 10.1137/S0895480102417768. 
Received 28 March 2007
Revised 24 September 2007
Accepted 24 September 2007