Discussiones Mathematicae Graph Theory 27(1) (2007)
105123
doi: 10.7151/dmgt.1348
Mustapha Kchikech, Riadh Khennoufa and Olivier Togni
LE2I, UMR CNRS 5158
Université de Bourgogne
21078 Dijon cedex, France
email: {kchikech, khennoufa, otogni}@ubourgogne.fr

for any two distinct vertices x and y, where d_{G}(x,y) is the distance between x and y in G. A cyclic klabeling 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 klabeling number of G is the minimum span of a linear (cyclic, respectively) radio klabeling of G.
In this paper, linear and cyclic radio klabeling numbers of paths, stars and trees are studied. For the path P_{n} of order n ≤ k+1, we completely determine the cyclic and linear radio klabeling numbers. For 1 ≤ k ≤ n−2, a new improved lower bound for the linear radio klabeling number is presented. Moreover, we give the exact value of the linear radio klabeling number of stars and we present an upper bound for the linear radio klabeling number of trees.
Keywords: graph theory, radio channel assignment, cyclic and linear radio klabeling.
2000 Mathematics Subject Classification: 05C15, 05C78.
[1]  G. Chartrand, D. Erwin and P. Zhang, Radio antipodal colorings of cycles, in: Proceedings of the Thirtyfirst Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 2000) 144 (2000) 129141. 
[2]  G. Chartrand, D. Erwin and P. Zhang, Radio antipodal colorings of graphs, Math. Bohem. 127 (2002) 5769. 
[3]  G. Chartrand, D. Erwin, P. Zhang and F. Harary, Radio labelings of graphs, Bull. Inst. Combin. Appl. 33 (2001) 7785. 
[4]  G. Chartrand, L. Nebeský and P. Zhang, Radio kcolorings of paths, Discuss. Math. Graph Theory 24 (2004) 521, doi: 10.7151/dmgt.1209. 
[5]  G. Chartrand, T. Thomas and P. Zhang, A new look at Hamiltonian walks, Bull. Inst. Combin. Appl. 42 (2004) 3752. 
[6]  G. Chartrand, T. Thomas, P. Zhang and V. Saenpholphat, On the Hamiltonian number of a graph, Congr. Numer. 165 (2003) 5164. 
[7]  J.R. Griggs and R.K. Yeh, Labelling graphs with a condition at distance 2, SIAM J. Disc. Math. 5 (1992) 586595, doi: 10.1137/0405048. 
[8]  J. van den Heuvel, R. Leese and M. Shepherd, Graph labeling and radio channel assignment, J. Graph Theory 29 (1998) 263283, doi: 10.1002/(SICI)10970118(199812)29:4<263::AIDJGT5>3.0.CO;2V. 
[9]  M. Kchikech, R. Khennoufa and O. Togni, Radio klabelings for cartesian products of graphs, in: Proceedings of the 7th International Conference on Graph Theory (ICGT'05), Electronic Notes in Discrete Mathematics 22 (2005) 347352. Extended version submited to Discrete Mathematics, doi: 10.1016/j.endm.2005.06.078. 
[10]  R. Khennoufa and O. Togni, A note on radio antipodal colourings of paths, Math. Bohemica 130 (2005) 277282. 
[11]  D. Král, L.D. Tong and X. Zhu, Upper Hamiltonian numbers and Hamiltonian spectra of graphs, Australasian J. Combin. 35 (2006) 329340. 
[12]  R.A. Leese and S.D. Noble, Cyclic labellings with constraints at two distances, The Electronic Journal of Combinatorics 11 (2004). 
[13]  D. Liu and X. Zhu, Multilevel distance labelings for paths and cycles, SIAM J. Discrete Math. 19 (2005) 610621, doi: 10.1137/S0895480102417768. 
[14]  V. Saenpholphat, F. Okamoto and P. Zhang, Measures of traceability in graphs, Math. Bohemica 131 (2006) 6384. 
[15]  N. Schabanel, Radio Channel Assignment, (PhD Thesis, Merton College Oxford, 1998). 
Received 12 December 2005
Revised 26 August 2006