PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2008 | 28 | 1 | 165-178
Tytuł artykułu

Radio k-labelings for Cartesian products of graphs

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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 max{f(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].
Wydawca
Rocznik
Tom
28
Numer
1
Strony
165-178
Opis fizyczny
Daty
wydano
2008
otrzymano
2007-03-28
poprawiono
2007-09-24
zaakceptowano
2007-09-24
Twórcy
  • LE2I, UMR CNRS 5158, Université de Bourgogne, 21078 Dijon cedex, France
  • LE2I, UMR CNRS 5158, Université de Bourgogne, 21078 Dijon cedex, France
  • LE2I, UMR CNRS 5158, Université de Bourgogne, 21078 Dijon cedex, France
Bibliografia
  • [1] G. Chartrand, D. Erwin and P. Zhang, Radio antipodal colorings of cycles, Congr. Numer. 144 (2000) 129-141.
  • [2] G. Chartrand, D. Erwin and P. Zhang, Radio antipodal colorings of graphs, Math. Bohem. 127 (2002) 57-69.
  • [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.
  • [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.
  • [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).
  • [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.
  • [7] R. Khennoufa and O. Togni, A note on radio antipodal colourings of paths, Math. Bohemica 130 (2005) 277-282.
  • [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) 329-340.
  • [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, Multi-level distance labelings for paths and cycles, SIAM J. Discrete Math. 19 (2005) 610-621, doi: 10.1137/S0895480102417768.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1399
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.