- Tytuł:
- Linear and cyclic radio k-labelings of trees
- Autorzy:
-
Kchikech, Mustapha
Khennoufa, Riadh
Togni, Olivier - Powiązania:
- https://bibliotekanauki.pl/articles/743693.pdf
- Data publikacji:
- 2007
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
graph theory
radio channel assignment
cyclic and linear radio k-labeling - Opis:
-
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. - Źródło:
-
Discussiones Mathematicae Graph Theory; 2007, 27, 1; 105-123
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł