LAPLACIAN PERMANENTS OF TREES

Let T be a tree on n vertices. The Laplacian matrix L(T) is the difference of the diagonal matrix of vertex degrees and the adjacency matrix. The main result of this article is that, for "almost all" trees T, there is a nonisomorphic tree T' such that per L (T) = per L (T'). The proof follows the approach taken by Schwenk in [New Directions in the Theory of Graphs, F. Harary, ed., Academic Press, New York, 1973, pp. 275-307]. The difficulty is finding a single pair of "super" trees from which to start. The search for this pair was greatly facilitated by a new algorithm for computing Laplacian permanents of trees. This algorithm is also reported. Finally, the algorithm is used to establish inequalities for per L(T).