Radio k-colorings of paths

Gary Chartrand; Ladislav Nebeský; Ping Zhang

Discussiones Mathematicae Graph Theory (2004)

  • Volume: 24, Issue: 1, page 5-21
  • ISSN: 2083-5892

Abstract

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

How to cite

top

Gary Chartrand, Ladislav Nebeský, and Ping Zhang. "Radio k-colorings of paths." Discussiones Mathematicae Graph Theory 24.1 (2004): 5-21. <http://eudml.org/doc/270733>.

@article{GaryChartrand2004,
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 $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.},
author = {Gary Chartrand, Ladislav Nebeský, Ping Zhang},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {radio k-coloring; radio k-chromatic number; radio -coloring; -chromatic number; path},
language = {eng},
number = {1},
pages = {5-21},
title = {Radio k-colorings of paths},
url = {http://eudml.org/doc/270733},
volume = {24},
year = {2004},
}

TY - JOUR
AU - Gary Chartrand
AU - Ladislav Nebeský
AU - Ping Zhang
TI - Radio k-colorings of paths
JO - Discussiones Mathematicae Graph Theory
PY - 2004
VL - 24
IS - 1
SP - 5
EP - 21
AB - 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.
LA - eng
KW - radio k-coloring; radio k-chromatic number; radio -coloring; -chromatic number; path
UR - http://eudml.org/doc/270733
ER -

References

top
  1. [1] G. Chartrand, D. Erwin, F. Harary and P. Zhang, Radio labelings of graphs, Bull. Inst. Combin. Appl. 33 (2001) 77-85. Zbl0989.05102
  2. [2] G. Chartrand, D. Erwin and P. Zhang, A graph labeling problem suggested by FM channel restrictions, Bull. Inst. Combin. Appl. (accepted). Zbl1066.05125
  3. [3] G. Chartrand, D. Erwin and P. Zhang, Radio antipodal colorings of cycles, Congr. Numer. 144 (2000) 129-141. Zbl0976.05028
  4. [4] G. Chartrand, D. Erwin and P. Zhang, Radio antipodal colorings of graphs, Math. Bohem. 127 (2002) 57-69. Zbl0995.05056
  5. [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. Zbl0929.68005
  6. [6] W. Hale, Frequency assignment: theory and applications, Proc. IEEE 68 (1980) 1497-1980, doi: 10.1109/PROC.1980.11899. 
  7. [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 Zbl0930.05087
  8. [8] Minimum distance separation between stations, Code of Federal Regulations, Title 47, sec. 73.207. 

Citations in EuDML Documents

top
  1. Riadh Khennoufa, Olivier Togni, A note on radio antipodal colourings of paths
  2. Yu-Fa Shen, Guo-Ping Zheng, Wen-Jie HeK, Improved upper bounds for nearly antipodal chromatic number of paths
  3. Mustapha Kchikech, Riadh Khennoufa, Olivier Togni, Radio k-labelings for Cartesian products of graphs
  4. Srinivasa Rao Kola, Pratima Panigrahi, Nearly antipodal chromatic number a c ' ( P n ) of the path P n
  5. Mustapha Kchikech, Riadh Khennoufa, Olivier Togni, Linear and cyclic radio k-labelings of trees
  6. Futaba Fujie-Okamoto, Willem Renzema, Ping Zhang, The k -metric colorings of a graph

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.