Evaluation of the characteristic polynomial of a graph (Q1310247)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Evaluation of the characteristic polynomial of a graph |
scientific article |
Statements
Evaluation of the characteristic polynomial of a graph (English)
0 references
16 January 1994
0 references
The author adapts the classical ``Le Verrier-Faddeev-Frame'' method for the evaluation of the characteristic polynomial of a graph by first diagonalizing the adjacency matrix. The resulting technique can be shown to be \(O(n^ 3)\) instead of \(O(n^ 4)\). The author also shows how to efficiently find (in \((O(n^ 2)))\) the characteristic polynomial from the known eigenvalues of the adjacency matrix.
0 references
evaluation
0 references
characteristic polynomial
0 references
adjacency matrix
0 references
eigenvalues
0 references
