Deakin University
Browse
- No file added yet -

Optimal radio labellings of complete m-ary trees

Download (676.69 kB)
journal contribution
posted on 2010-03-06, 00:00 authored by X Li, Vicky MakVicky Mak, S Zhou
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 maxu, v V (G) | 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.

History

Journal

Discrete applied mathematics

Volume

158

Pagination

507 - 515

Location

Amsterdam, Netherlands

Open access

  • Yes

ISSN

0166-218X

eISSN

1872-6771

Language

eng

Publication classification

C1 Refereed article in a scholarly journal

Copyright notice

2009, Elsevier B.V. All rights reserved.