| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4649379 | Discrete Mathematics | 2009 | 7 Pages |
Abstract
The antibandwidth problem is to label vertices of a nn-vertex graph injectively by 1,2,3,…n1,2,3,…n, so that the minimum difference between labels of adjacent vertices is maximised. The problem is motivated by the obnoxious facility location problem, radiocolouring, work and game scheduling and is dual to the well known bandwidth problem. We prove exact results for the antibandwidth of complete kk-ary trees, kk even, and estimate the parameter for odd kk up to the second order term. This extends previous results for complete binary trees.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Tiziana Calamoneri, Annalisa Massini, L’ubomír Török, Imrich Vrt’o,