Computing the characteristic polynomial of a tree (Q1057861)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Computing the characteristic polynomial of a tree |
scientific article |
Statements
Computing the characteristic polynomial of a tree (English)
0 references
1985
0 references
An \(O(n^ 3)\)-algorithm for computing the characteristic polynomial of a tree (i.e. of its adjacency matrix) is presented. A by-product is the minimal polynomial of the considered tree. It is shown that both polynomials are presented by the algorithm in a factorized form where the degree of the factors is minimal with respect to certain structural properties of the tree.
0 references
spectra of graphs
0 references
factorizations
0 references
algorithm
0 references
characteristic polynomial
0 references
tree
0 references
minimal polynomial
0 references
