Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: cyclic and linear radio k-labeling

Sortuj według:

Ogranicz wyniki do:

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

Linear and cyclic radio k-labelings of trees

100%

Kchikech M., Khennoufa R., Togni O.

Discussiones Mathematicae Graph Theory

2007

tom 27

nr 1

105-123

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.

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Kchikech M.

1 Khennoufa R.

1 Togni O.

1 2007

Wyniki wyszukiwania

Linear and cyclic radio k-labelings of trees