How to Construct the Characteristic Polynomial of a Tree's Adjacency Matrix

We describe a simple, O(n 2 log(n)) algorithm to find the characteristic polynomial of the adjacency matrix of any tree. An example is given showing the algorithm applied to a 13-vertex tree. key words: tree, adjacency matrix, characteristic polynomial. 1 Introduction Let G = (V; E) be an undirected graph with vertices V = (v 1 ; : : : ; v n ) and edge set E. Edges occur only between pairs of distinct vertices, and between any pair of vertices there is at most one edge. The adjacency matrix A = [a ij ] of G is the n \Theta n 0-1 matrix for which a ij = 1 if and only if v i is adjacent to v j (that is, there is an edge between v i and v j ). In this paper, a graph is always a tree (i.e., a connected, acyclic graph) or a forest (i.e., a disjoint collection of trees). The first author thanks CNPq and Clemson University for the support to visit UFRGS while this research was performed. y The second author also thanks CNPq for support during this period. D. P. Jacobs and V. Trev..