Optimal radio labellings of complete m-ary trees
Data(s) |
06/03/2010
|
---|---|
Resumo |
A radio labelling of a connected graph G is a mapping f : V (G) → {0, 1, 2, ...} such that | f (u) - f (v) | ≥ diam (G) - d (u, v) + 1 for each pair of distinct vertices u, v ∈ V (G), where diam (G) is the diameter of G and d (u, v) the distance between u and v. The span of f is defined as max<sub>u</sub>, <sub>v</sub> <sub>∈</sub> <sub>V</sub> <sub>(G) </sub>| f (u) - f (v) |, and the radio number of G is the minimum span of a radio labelling of G. A complete m-ary tree (m ≥ 2) is a rooted tree such that each vertex of degree greater than one has exactly m children and all degree-one vertices are of equal distance (height) to the root. In this paper we determine the radio number of the complete m-ary tree for any m ≥ 2 with any height and construct explicitly an optimal radio labelling.<br /> |
Identificador | |
Idioma(s) |
eng |
Publicador |
Elsevier BV |
Relação |
http://dro.deakin.edu.au/eserv/DU:30033648/mak-optimalradio-2010.pdf http://dx.doi.org/10.1016/j.dam.2009.11.014 |
Direitos |
2009, Elsevier B.V. All rights reserved. |
Tipo |
Journal Article |