Bandwidths and profiles of trees (Q1073038)

The bandwidths of labelled, rooted trees are studied. It is shown that the average bandwidth of trees of n vertices is \(>C_ 1\sqrt{n}\) and \(<C_ 2\sqrt{n \log n}\). The width of such a tree is the largest number of vertices at a constant distance from the root. The distribution of the width and its relationship with the bandwidth are studied. Results include generating functions for trees by width, and asymptotic estimates. [See also P. Kirschenhofer's review of the authors' conference article with the same title published in Graph theory with applications to algorithms and computer science, Proc. 5th Int. Conf., Kalamazoo/Mich. 1984, 605-622 (1985; Zbl 0575.05023).]