Similarly, the characteristic polynomial of a matrix is
where Einstein summation has been used, which
can also be written explicitly in terms of traces as
In general, the characteristic polynomial has the form
is the matrix trace of the matrix , , and is the sum of the -rowed diagonal minors of the matrix (Jacobson 1974, p. 109).
Le Verrier's algorithm for computing the characteristic polynomial of a graph (Balasubramanian 1984; Trinajstić 1988; Ivanciuc and Balaban 2000, p. 89) can be formulated as the solution of the linear system
An algorithm due to Balasubramanian computes using the equation
(Balasubramanian 1985, 1985, 1991; Ivanciuc and Balaban 2000, p. 90; typo corrected) with
The characteristic polynomial of a graph is defined as the characteristic polynomial of its adjacency
matrix and can be computed in the Wolfram
Language using CharacteristicPolynomial[AdjacencyMatrix[g],
x]. The precomputed characteristic polynomial of a named graph in terms of
can also be obtained using GraphData[graph,
Characteristic polynomials are not diagnostic for graph isomorphism, i.e., two nonisomorphic graphs may share the same characteristic
polynomial. The smallest such example occurs for the two graphs on five nodes illustrated
above, both of which have characteristic polynomial . The number of distinct characteristic polynomials
for simple undirected graphs on , 2, ... nodes are 1, 2, 4, 11, 33, 151, 988, 11453, ...
(OEIS A082104), giving the number of duplicated
characteristic polynomials as 0, 0, 0, 0, 1, 5, 56, 893, 27311, ....
The following table summarizes the characteristic polynomials for some simple graphs.
Balasubramanian, K. "Computer-Generation of the Characteristic-Polynomials of Chemical Graphs." J. Comput. Chem.5, 387-394, 1984.Balasubramanian,
K. "The Use of Frames Method for the Characteristic-Polynomials of Chemical
Graphs." Theor. Chim. Acta65, 49-58, 1984.Balasubramanian,
K. "Computer-Assisted Enumeration of Walks and Self-Returning Walks on Chemical
Graphs." Comput. Chem.9, 43-52, 1985.Balasubramanian,
K. "Comments on the Characteristic Polynomial of a Graph." J. Comput.
Chem.12, 248-253, 1991.Devillers, J. and Balaban, A. T.
Indices and Related Descriptors in QSAR and QSPR. Amsterdam, Netherlands:
Gordon and Breach, pp. 83-92, 2000.Golub, G. H. and Van Loan,
C. F. Matrix
Computations, 3rd ed. Baltimore, MD: Johns Hopkins University Press, p. 310,
1996.Hagos, E. M. "The Characteristic Polynomial of a Graph
is Reconstructible from the Characteristic Polynomials of its Vertex-Deleted Subgraphs
and Their Complements." Elec. J. Combin.7, No. 1, R12, 1-9,
P. "Chemical Graph Polynomials. Part 2. The Propagation Diagram Algorithm for
the Computation of the Characteristic Polynomial of Molecular Graphs." Rev.
Roumaine Chim.37, 1341-134, 1992.Ivanciuc, O. and Balaban,
A. T. "The Graph Description of Chemical Structures." Ch. 3 in
Indices and Related Descriptors in QSAR and QSPR (Ed. J. Devillers and
A. T. Balaban). Amsterdam, Netherlands: Gordon and Breach, pp. 59-167,
2000.Jacobson, N. Basic
Algebra I. San Francisco: W. H. Freeman, 1974.Krivka,
P.; Jeričević, .; and Trinajstić, N. "On the Computation
of Characteristic Polynomial of a Chemical Graph." Int. J. Quant. Chem.:
Quant. Chem. Symp.19, 129-147, 1986.Sloane, N. J. A.
Sequence A082104 in "The On-Line Encyclopedia
of Integer Sequences."Trinajstić, N. "The Characteristic
Polynomial of a Chemical Graph." J. Math. Chem.2, 197-215, 1988.Zivković,
T. "On the Evaluation of the Characteristic Polynomial of a Chemical Graph."
J. Comput. Chem.11, 217-222, 1990.