Evaluation of the characteristic polynomial of a graph (Q1310247)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 475052
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Evaluation of the characteristic polynomial of a graph |
scientific article; zbMATH DE number 475052 |
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
0.8217611312866211
0 references
0.8036825060844421
0 references
0.7946763038635254
0 references
