We determine, constructively, the bandwidth of the complete k-ary tree on d levels. By rectifying an algorithm of Chung (1988), we establish B( Tk,J = rk(kd -1)/(2d( k -1)) 1.
1. Praeludium
The bandwidth problem for a graph G is a question about numbering the vertices of G so the maximum difference between the numbers on adjacent vertices is minimal. We will call a l-l function f: V(G) + Z a proper numbering of G. The 'bandwidth of a proper numbering J denoted B,(G), is given by The bandwidth of G, written B(G), is defined as
At lower bound on the bandwidth of any graph G is easily obtained by considering how far apart the lowest and highest numbered vertices can be. Thus we have
Chung [l] claims that for Tk,d, the complete k-ary tree with d levels and kd leaves, the bandwidth assumes this lower bound; i.e. B( Tk,d) = rk(kdl)/(k -1)(2d)J She gives an algorithm for labelling Tk,d that is purported to obtain the minimal bandwidth. Her method is essentially this: suppose the bandwidth is X; on each pass we label x vertices, first numbering the parents of vertices numbered on the previous pass, the lower numbered vertex receiving the lower numbered parent, and then assigning the remaining numbers to the leftmost available leaves; (note that on the first pass, the