# Linear and cyclic radio k-labelings of trees

Mustapha Kchikech; Riadh Khennoufa; Olivier Togni

Discussiones Mathematicae Graph Theory (2007)

- Volume: 27, Issue: 1, page 105-123
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topMustapha Kchikech, Riadh Khennoufa, and Olivier Togni. "Linear and cyclic radio k-labelings of trees." Discussiones Mathematicae Graph Theory 27.1 (2007): 105-123. <http://eudml.org/doc/270675>.

@article{MustaphaKchikech2007,

abstract = {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.},

author = {Mustapha Kchikech, Riadh Khennoufa, Olivier Togni},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {graph theory; radio channel assignment; cyclic and linear radio k-labeling; cyclic and linear radio -labeling},

language = {eng},

number = {1},

pages = {105-123},

title = {Linear and cyclic radio k-labelings of trees},

url = {http://eudml.org/doc/270675},

volume = {27},

year = {2007},

}

TY - JOUR

AU - Mustapha Kchikech

AU - Riadh Khennoufa

AU - Olivier Togni

TI - Linear and cyclic radio k-labelings of trees

JO - Discussiones Mathematicae Graph Theory

PY - 2007

VL - 27

IS - 1

SP - 105

EP - 123

AB - 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.

LA - eng

KW - graph theory; radio channel assignment; cyclic and linear radio k-labeling; cyclic and linear radio -labeling

UR - http://eudml.org/doc/270675

ER -

## References

top- [1] G. Chartrand, D. Erwin and P. Zhang, Radio antipodal colorings of cycles, in: Proceedings of the Thirty-first Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 2000) 144 (2000) 129-141. Zbl0976.05028
- [2] G. Chartrand, D. Erwin and P. Zhang, Radio antipodal colorings of graphs, Math. Bohem. 127 (2002) 57-69. Zbl0995.05056
- [3] G. Chartrand, D. Erwin, P. Zhang and F. Harary, Radio labelings of graphs, Bull. Inst. Combin. Appl. 33 (2001) 77-85. Zbl0989.05102
- [4] G. Chartrand, L. Nebeský and P. Zhang, Radio k-colorings of paths, Discuss. Math. Graph Theory 24 (2004) 5-21, doi: 10.7151/dmgt.1209. Zbl1056.05053
- [5] G. Chartrand, T. Thomas and P. Zhang, A new look at Hamiltonian walks, Bull. Inst. Combin. Appl. 42 (2004) 37-52. Zbl1056.05093
- [6] G. Chartrand, T. Thomas, P. Zhang and V. Saenpholphat, On the Hamiltonian number of a graph, Congr. Numer. 165 (2003) 51-64. Zbl1043.05041
- [7] J.R. Griggs and R.K. Yeh, Labelling graphs with a condition at distance 2, SIAM J. Disc. Math. 5 (1992) 586-595, doi: 10.1137/0405048. Zbl0767.05080
- [8] J. van den Heuvel, R. Leese and M. 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
- [9] M. Kchikech, R. Khennoufa and O. Togni, Radio k-labelings for cartesian products of graphs, in: Proceedings of the 7th International Conference on Graph Theory (ICGT'05), Electronic Notes in Discrete Mathematics 22 (2005) 347-352. Extended version submited to Discrete Mathematics, doi: 10.1016/j.endm.2005.06.078. Zbl1200.05200
- [10] R. Khennoufa and O. Togni, A note on radio antipodal colourings of paths, Math. Bohemica 130 (2005) 277-282. Zbl1110.05033
- [11] D. Král, L.-D. Tong and X. Zhu, Upper Hamiltonian numbers and Hamiltonian spectra of graphs, Australasian J. Combin. 35 (2006) 329-340. Zbl1095.05023
- [12] R.A. Leese and S.D. Noble, Cyclic labellings with constraints at two distances, The Electronic Journal of Combinatorics 11 (2004). Zbl1053.05111
- [13] D. Liu and X. Zhu, Multi-level distance labelings for paths and cycles, SIAM J. Discrete Math. 19 (2005) 610-621, doi: 10.1137/S0895480102417768. Zbl1095.05033
- [14] V. Saenpholphat, F. Okamoto and P. Zhang, Measures of traceability in graphs, Math. Bohemica 131 (2006) 63-84. Zbl1112.05032
- [15] N. Schabanel, Radio Channel Assignment, (PhD Thesis, Merton College Oxford, 1998). Zbl0930.05087

## Citations in EuDML Documents

top## NotesEmbed ?

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