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

Linear and cyclic radio k-labelings of trees

Abstract : Motivated by problems in radio channel assignments, we consider radio k-labelings of graphs. For a connected graph G and an integer k ≥ 1, a linear radio k-labeling of G is an assignment f of nonnegative integers to the vertices of G such that |f(x)−f(y)| ≥ k+1−dG(x,y), for any two distinct vertices x and y, where dG(x,y) is the distance between x and y in G. A cyclic k-labeling of G is defined analogously by using the cyclic metric on the labels. In both cases, we are interested in minimizing the span of the labeling. The linear (cyclic, respectively) radio k-labeling number of G is the minimum span of a linear (cyclic, respectively) radio k-labeling of G. In this paper, linear and cyclic radio k-labeling numbers of paths, stars and trees are studied. For the path Pn of order n ≤ k+1, we completely determine the cyclic and linear radio k-labeling numbers. For 1 ≤ k ≤ n−2, a new improved lower bound for the linear radio k-labeling number is presented. Moreover, we give the exact value of the linear radio k-labeling number of stars and we present an upper bound for the linear radio k-labeling number of trees.
Type de document :
Article dans une revue
Liste complète des métadonnées
Contributeur : Olivier Togni <>
Soumis le : lundi 2 janvier 2012 - 07:45:19
Dernière modification le : vendredi 17 juillet 2020 - 14:54:04


  • HAL Id : hal-00655729, version 1


Mustapha Kchikech, Riadh Khennoufa, Olivier Togni. Linear and cyclic radio k-labelings of trees. Discussiones Mathematicae Graph Theory, University of Zielona Góra, 2007, 27 (1), p. 105-123. ⟨hal-00655729⟩



Consultations de la notice