Separation numbers of trees

Let G be a graph on n vertices. Given a bijection f:V(G)→{1,2,…,n}, let |f|=min{|f(u)−f(v)|:uv∈E(G)}. The separation number s(G) (also known as antibandwidth [T. Calamoneri, A. Massini, L. Török, 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. Török, I. Vrt’o, Antibandwidth and cyclic antibandwidth of meshes and hypercubes, Discrete Mathematics 309 (2009) 3541–3552] of G is then max{|f|} over all 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 , where μ is the minimum value of ‖X|−|Y‖ over all bipartitions (X,Y) of F.2.Let d be the maximum degree of a tree T on n vertices. Then (a), and(b), where c1 and c2 are absolute constants.We give constructions showing that the bound (a) is asymptotically tight when d is in the range , while (b) is asymptotically tight when d is in the range , where is any fixed constant, and when d≥4 is an absolute constant.We also show that for h≥3 and odd d≥3, we have , where is the symmetric d-ary tree of height h, improving the estimates obtained in the first of the above-mentioned references.