Separation numbers of trees
Let G be a graph on n vertices. Given a bijection f : V(G) -> {1, 2, ... , n}, let vertical bar f vertical bar = mini{vertical bar f(u) - f(v)vertical bar : uv is an element of E(G)}. The separation number s(G) (also known as antibandwidth [T. Calamoneri, A. Massini, L. Torok, I. Vrt'o, Antibandwidth of Complete k-ary trees, Electronic Notes in Discrete Mathematics 24 (2006), 259-266; A. Raspaud, H. Schroder, O. Sykora, L Torok, I. Vrt'o, Antibandwidth and cyclic antibandwidth of meshes and hypercubes, Discrete Mathematics 309(2009)3541-3552] of G is then max{vertical bar f vertical bar} overall such bijections f of G. We study the case when G is a forest, obtaining the following results. 1. Let F be a forest in which each component is a star. Then s(F) = n-mu/2, where mu is the minimum value of parallel to X vertical bar - vertical bar Y parallel to over all bipartitions (X, Y) of F. 2. Let d be the maximum degree of a tree T on n vertices. Then (a) s(T) >= n/2 - c(1) root nd, and (b) s(T) >= n/2 - c(2)d(2) log(d)n, where c(1) and c(2) are absolute constants. We give constructions showing that the bound (a) is asymptotically right when d is in the range n(1/3)  = 4 is an absolute constant. We also show that for h >= 3 and odd d >= 3, we have s(T(h)(d)) = n/2 - Theta(d(2) + dh), where T(h)(d) is the symmetric d-ary tree of height h, improving the estimates obtained in the first of the above-mentioned references. (C) 2009 Elsevier B.V. All rights reserved.
separation antibandwidth bandwidth labeling