Editing Spectral graph theory (section)

==Cospectral graphs==
Two graphs are called '''cospectral''' or '''isospectral''' if the adjacency matrices of the graphs are [[isospectral]], that is, if the adjacency matrices have equal [[multiset]]s of eigenvalues.

[[File:Isospectral enneahedra.svg|thumb|300px|Two cospectral [[enneahedron|enneahedra]], the smallest possible cospectral [[polyhedral graph]]s]]
Cospectral graphs need not be [[Graph isomorphism|isomorphic]], but isomorphic graphs are always cospectral.

=== Graphs determined by their spectrum ===
A graph <math>G</math> is said to be determined by its spectrum if any other graph with the same spectrum as <math>G</math> is isomorphic to <math>G</math>.

Some first examples of families of graphs that are determined by their spectrum include:
* The [[complete graph]]s.
* The finite [[starlike tree]]s.

=== Cospectral mates ===
A pair of graphs are said to be cospectral mates if they have the same spectrum, but are non-isomorphic.

The smallest pair of cospectral mates is {''K''<sub>1,4</sub>, ''C''<sub>4</sub> ∪ ''K''<sub>1</sub>}, comprising the 5-vertex [[star (graph theory)|star]] and the [[graph union]] of the 4-vertex [[cycle (graph theory)|cycle]] and the single-vertex graph.<ref>{{mathworld|CospectralGraphs|Cospectral Graphs}}</ref> The first example of cospectral graphs was reported by Collatz and Sinogowitz<ref>Collatz, L. and Sinogowitz, U. "Spektren endlicher Grafen." Abh. Math. Sem. Univ. Hamburg 21, 63–77, 1957.</ref> in 1957.

The smallest pair of [[polyhedral graph|polyhedral]] cospectral mates are [[enneahedron|enneahedra]] with eight vertices each.<ref>{{citation|title=Topological twin graphs. Smallest pair of isospectral polyhedral graphs with eight vertices|year=1994|last1=Hosoya|last2=Nagashima|last3=Hyugaji|first1=Haruo|first2=Umpei|first3=Sachiko|author1-link=Haruo Hosoya|journal=Journal of Chemical Information and Modeling|volume=34|issue=2|pages=428–431|doi=10.1021/ci00018a033}}.</ref>

=== Finding cospectral graphs ===
[[Almost all]] [[tree (graph theory)|tree]]s are cospectral, i.e., as the number of vertices grows, the fraction of trees for which there exists a cospectral tree goes to 1.{{sfnp|Schwenk|1973|pages =275-307}}

A pair of [[regular graph]]s are cospectral if and only if their complements are cospectral.<ref>{{Cite web|url=http://www.math.uwaterloo.ca/~cgodsil/pdfs/cospectral.pdf|title=Are Almost All Graphs Cospectral?|last=Godsil|first=Chris|date=November 7, 2007}}</ref>

A pair of [[distance-regular graph]]s are cospectral if and only if they have the same intersection array.

Cospectral graphs can also be constructed by means of the [[isospectral|Sunada method]].<ref>{{citation
 | last = Sunada | first = Toshikazu | journal = Ann. of Math.
 | pages = 169–186
 | title = Riemannian coverings and isospectral manifolds
 | volume = 121
 | issue = 1 | year = 1985
 | doi = 10.2307/1971195 | jstor = 1971195 }}.</ref>

Another important source of cospectral graphs are the point-collinearity graphs and the line-intersection graphs of [[incidence geometry|point-line geometries]]. These graphs are always cospectral but are often non-isomorphic.<ref>{{harvnb|Brouwer|Haemers|2011}}</ref>