Frequency planning consists in allocating frequencies to the transmitters of a cellular network so as to ensure that no pair of transmitters interfere. We study the problem of reducing interference by modeling this by a radio k-labeling problem on graphs: For a graph G and an integer k ≥ 1, a radio k-labeling of G is an assignment f of non negative integers to the vertices of G such that , for any two vertices x and y, where is the distance between x and y in G. The radio k-chromatic number is the minimum of maxf(x)-f(y):x,y ∈ V(G) over all radio k-labelings f of G. In this paper we present the radio k-labeling for the Cartesian product of two graphs, providing upper bounds on the radio k-chromatic number for this product. These results help to determine upper and lower bounds for radio k-chromatic 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].
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1399,
author = {Mustapha Kchikech and Riadh Khennoufa and Olivier Togni},
title = {Radio k-labelings for Cartesian products of graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {28},
year = {2008},
pages = {165-178},
zbl = {1171.05020},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1399}
}
Mustapha Kchikech; Riadh Khennoufa; Olivier Togni. Radio k-labelings for Cartesian products of graphs. Discussiones Mathematicae Graph Theory, Tome 28 (2008) pp. 165-178. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1399/
[000] [1] G. Chartrand, D. Erwin and P. Zhang, Radio antipodal colorings of cycles, Congr. Numer. 144 (2000) 129-141. | Zbl 0976.05028
[001] [2] G. Chartrand, D. Erwin and P. Zhang, Radio antipodal colorings of graphs, Math. Bohem. 127 (2002) 57-69. | Zbl 0995.05056
[002] [3] G. Chartrand, L. Nebeský and P. Zhang, Radio k-colorings of paths, Discuss. Math. Graph Theory 24 (2004) 5-21, doi: 10.7151/dmgt.1209. | Zbl 1056.05053
[003] [4] G. Fertin, E. Godard and A. Raspaud, Acyclic and k-distance coloring of the grid, Inform. Process. Lett. 87 (2003) 51-58, doi: 10.1016/S0020-0190(03)00232-1. | Zbl 1175.68293
[004] [5] W. Imrich and S. Klavžar, Product graphs, Structure and recognition, With a foreword by Peter Winkler, Wiley-Interscience Series in Discrete Mathematics and Optimization (Wiley-Interscience, New York, 2000). | Zbl 0963.05002
[005] [6] M. Kchikech, R. Khennoufa and O. Togni, Linear and cyclic radio k-labelings of trees, Discuss. Math. Graph Theory 27 (2007) 105-123, doi: 10.7151/dmgt.1348. | Zbl 1137.05063
[006] [7] R. Khennoufa and O. Togni, A note on radio antipodal colourings of paths, Math. Bohemica 130 (2005) 277-282. | Zbl 1110.05033
[007] [8] R. Khennoufa and O. Togni, The Radio Antipodal Number of the Hypercube, submitted, 2007. | Zbl 1265.05536
[008] [9] D. Král, L.-D. Tong and X. Zhu, Upper Hamiltonian numbers and Hamiltonian spectra of graphs, Australasian J. Combin. 35 (2006) 329-340. | Zbl 1095.05023
[009] [10] D. Liu, Radio Number for Trees, manuscript, 2006.
[010] [11] D. Liu and M. Xie, Radio Number for Square Paths, Discrete Math., to appear. | Zbl 1224.05451
[011] [12] D. Liu and X. Zhu, Multi-level distance labelings for paths and cycles, SIAM J. Discrete Math. 19 (2005) 610-621, doi: 10.1137/S0895480102417768. | Zbl 1095.05033