Spectral graph theory: Difference between revisions

Revision as of 00:43, 30 December 2004

Revision as of 00:45, 30 December 2004

Line 5:

Let ''M'' be the [[adjacency matrix]] of a graph.

The [[charactereristiccharacteristic polynomial]] of the graph is

:''p''_''M''(''t'') = [[determinant|det]](''M'' - ''tI'')

Given a particular polynomial, it is not known if a corresponding adjacency matrix can be deduced. Two graphs are said to be [[isospectral]] if the adjacency matrices of the graphs have the same eigenvalues. Isospectral graphs need not be [[isomorphic]], but isomorphic graphs are always isospectral, because the