alpha-labeling number of trees

Abstract

In this paper, we prove that the alpha-labeling number of trees T, T-alpha <= [r/2] n where n = vertical bar E(T)vertical bar and r is the radius of T. This improves the known result T-alpha <= e(O(root nlogn)) tremendously and this upper bound is very close to the upper bound T-alpha <= n conjectured by Snevily. Moreover, we prove that a tree with n edges and radius r decomposes K-1 for some t <= (r + 1)n(2) + 1. (c) 2006 Elsevier B.V. All rights reserved.