The typenumber of trees

Abstract

This paper proves that the typenumber of a tree T is independent of the number of the pages in a book-embedding, and is equal to either D(T) or D(T) + 1, where D(T) is the set of integers which are degrees of the vertices of T. We then completely characterize trees having typenumber D(T) and trees having typenumber D(T) + 1. (C) 2002 Elsevier Science B.V. All rights reserved.