Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: radio k-chromatic number

Sortuj według:

Ogranicz wyniki do:

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

Radio k-colorings of paths

100%

Chartrand G., Nebeský L., Zhang P.

Discussiones Mathematicae Graph Theory

2004

tom 24

nr 1

5-21

For a connected graph G of diameter d and an integer k with 1 ≤ k ≤ d, a radio k-coloring of G is an assignment c of colors (positive integers) to the vertices of G such that d(u,v) + |c(u)- c(v)| ≥ 1 + k for every two distinct vertices u and v of G, where d(u,v) is the distance between u and v. The value rcₖ(c) of a radio k-coloring c of G is the maximum color assigned to a vertex of G. The radio k-chromatic number rcₖ(G) of G is the minimum value of rcₖ(c) taken over all radio k-colorings c of G. In this paper, radio k-colorings of paths are studied. For the path Pₙ of order n ≥ 9 and n odd, a new improved bound for $rc_{n- 2}(Pₙ)$ is presented. For n ≥ 4, it is shown that $rc_{n-3}(Pₙ) ≤ \binom{n-2} {2}$ Upper and lower bounds are also presented for rcₖ(Pₙ) in terms of k when 1 ≤ k ≤ n- 1. The upper bound is shown to be sharp when 1 ≤ k ≤ 4 and n is sufficiently large.

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Chartrand G.

1 Nebeský L.

1 Zhang P.

1 2004

Wyniki wyszukiwania

Radio k-colorings of paths