ArticleOriginal scientific text

Title

Radio k-colorings of paths

Authors 1, 2, 1

Affiliations

  1. Department of Mathematics, Western Michigan University, Kalamazoo, MI 49008, USA
  2. Faculty of Arts and Philosophy, Charles University, Prague nám. J. Palacha 2, CZ - 116 38 Praha 1, Czech Republic

Abstract

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 rcn-2(P) is presented. For n ≥ 4, it is shown that rcn-3(P)bom{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.

Keywords

radio k-coloring, radio k-chromatic number

Bibliography

  1. G. Chartrand, D. Erwin, F. Harary and P. Zhang, Radio labelings of graphs, Bull. Inst. Combin. Appl. 33 (2001) 77-85.
  2. G. Chartrand, D. Erwin and P. Zhang, A graph labeling problem suggested by FM channel restrictions, Bull. Inst. Combin. Appl. (accepted).
  3. G. Chartrand, D. Erwin and P. Zhang, Radio antipodal colorings of cycles, Congr. Numer. 144 (2000) 129-141.
  4. G. Chartrand, D. Erwin and P. Zhang, Radio antipodal colorings of graphs, Math. Bohem. 127 (2002) 57-69.
  5. D. Fotakis, G. Pantziou, G. Pentaris and P. Sprirakis, Frequency assignment in mobile and radio networks, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 45 (1999) 73-90.
  6. W. Hale, Frequency assignment: theory and applications, Proc. IEEE 68 (1980) 1497-1980, doi: 10.1109/PROC.1980.11899.
  7. J. van den Heuvel, R.A. Leese and M.A. Shepherd, Graph labeling and radio channel assignment, J. Graph Theory 29 (1998) 263-283, doi: 10.1002/(SICI)1097-0118(199812)29:4<263::AID-JGT5>3.0.CO;2-V
  8. Minimum distance separation between stations, Code of Federal Regulations, Title 47, sec. 73.207.
Pages:
5-21
Main language of publication
English
Received
2000-12-16
Accepted
2002-11-14
Published
2004
Exact and natural sciences