Accéder directement au contenu Accéder directement à la navigation
Article dans une revue

Radio k-Labelings for Cartesian Products of Graphs

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−dG(x,y), for any two vertices x and y, where dG(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].
Type de document :
Article dans une revue
Liste complète des métadonnées

https://hal-univ-bourgogne.archives-ouvertes.fr/hal-00655720
Contributeur : Olivier Togni <>
Soumis le : dimanche 1 janvier 2012 - 22:24:37
Dernière modification le : vendredi 17 juillet 2020 - 14:54:04

Identifiants

  • HAL Id : hal-00655720, version 1

Citation

Riadh Khennoufa, Mustapha Kchikech, Olivier Togni. Radio k-Labelings for Cartesian Products of Graphs. Discussiones Mathematicae Graph Theory, University of Zielona Góra, 2008, 28 (1), p. 165-178. ⟨hal-00655720⟩

Partager

Métriques

Consultations de la notice

408