Radio k-labelings for Cartesian products of graphs

Mustapha Kchikech; Riadh Khennoufa; Olivier Togni

Discussiones Mathematicae Graph Theory (2008)

  • Volume: 28, Issue: 1, page 165-178
  • ISSN: 2083-5892

Abstract

top
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 | f ( x ) - f ( y ) | ≥ k + 1 - d G ( x , y ) , for any two vertices x and y, where d G ( x , y ) 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].

How to cite

top

Mustapha Kchikech, Riadh Khennoufa, and Olivier Togni. "Radio k-labelings for Cartesian products of graphs." Discussiones Mathematicae Graph Theory 28.1 (2008): 165-178. <http://eudml.org/doc/270576>.

@article{MustaphaKchikech2008,
abstract = {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 $|f(x)-f(y)| ≥ k+1-d_G(x,y)$, for any two vertices x and y, where $d_G(x,y)$ 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].},
author = {Mustapha Kchikech, Riadh Khennoufa, Olivier Togni},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {graph theory; radio channel assignment; radio k-labeling; Cartesian product; radio number; antipodal number; radio -labeling},
language = {eng},
number = {1},
pages = {165-178},
title = {Radio k-labelings for Cartesian products of graphs},
url = {http://eudml.org/doc/270576},
volume = {28},
year = {2008},
}

TY - JOUR
AU - Mustapha Kchikech
AU - Riadh Khennoufa
AU - Olivier Togni
TI - Radio k-labelings for Cartesian products of graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2008
VL - 28
IS - 1
SP - 165
EP - 178
AB - 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 $|f(x)-f(y)| ≥ k+1-d_G(x,y)$, for any two vertices x and y, where $d_G(x,y)$ 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].
LA - eng
KW - graph theory; radio channel assignment; radio k-labeling; Cartesian product; radio number; antipodal number; radio -labeling
UR - http://eudml.org/doc/270576
ER -

References

top
  1. [1] G. Chartrand, D. Erwin and P. Zhang, Radio antipodal colorings of cycles, Congr. Numer. 144 (2000) 129-141. Zbl0976.05028
  2. [2] G. Chartrand, D. Erwin and P. Zhang, Radio antipodal colorings of graphs, Math. Bohem. 127 (2002) 57-69. Zbl0995.05056
  3. [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. Zbl1056.05053
  4. [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. Zbl1175.68293
  5. [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). Zbl0963.05002
  6. [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. Zbl1137.05063
  7. [7] R. Khennoufa and O. Togni, A note on radio antipodal colourings of paths, Math. Bohemica 130 (2005) 277-282. Zbl1110.05033
  8. [8] R. Khennoufa and O. Togni, The Radio Antipodal Number of the Hypercube, submitted, 2007. Zbl1265.05536
  9. [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. Zbl1095.05023
  10. [10] D. Liu, Radio Number for Trees, manuscript, 2006. 
  11. [11] D. Liu and M. Xie, Radio Number for Square Paths, Discrete Math., to appear. Zbl1224.05451
  12. [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. Zbl1095.05033

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.