Linear and cyclic radio k-labelings of trees

Mustapha Kchikech, Riadh Khennoufa, and Olivier Togni. "Linear and cyclic radio k-labelings of trees." Discussiones Mathematicae Graph Theory 27.1 (2007): 105-123. <http://eudml.org/doc/270675>.

@article{MustaphaKchikech2007,
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-d_G(x,y)$, for any two distinct vertices x and y, where $d_G(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 Pₙ 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.},
author = {Mustapha Kchikech, Riadh Khennoufa, Olivier Togni},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {graph theory; radio channel assignment; cyclic and linear radio k-labeling; cyclic and linear radio -labeling},
language = {eng},
number = {1},
pages = {105-123},
title = {Linear and cyclic radio k-labelings of trees},
url = {http://eudml.org/doc/270675},
volume = {27},
year = {2007},
}

TY - JOUR
AU - Mustapha Kchikech
AU - Riadh Khennoufa
AU - Olivier Togni
TI - Linear and cyclic radio k-labelings of trees
JO - Discussiones Mathematicae Graph Theory
PY - 2007
VL - 27
IS - 1
SP - 105
EP - 123
AB - 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-d_G(x,y)$, for any two distinct vertices x and y, where $d_G(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 Pₙ 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.
LA - eng
KW - graph theory; radio channel assignment; cyclic and linear radio k-labeling; cyclic and linear radio -labeling
UR - http://eudml.org/doc/270675
ER -