Spectral graph theory

While the adjacency matrix depends on the vertex labeling, its spectrum is a graph invariant, although not a complete one. Spectral graph theory is also concerned with graph parameters that are defined via multiplicities of eigenvalues of matrices associated to the graph, such as the Colin de Verdière number. Two graphs are called cospectral or isospectral if the adjacency matrices of the graphs are isospectral, that is, if the adjacency matrices have the same eigenvalues with multiplicity. Cospectral graphs need not be isomorphic, but isomorphic graphs are always cospectral. A graph G {\displaystyle G} is said to be determined by its spectrum if any other graph with the same spectrum as G {\displaystyle G} is isomorphic to G {\displaystyle G} . Some first examples of families of graphs that are determined by their spectrum include: Two graphs are said to be cospectral mates if they are cospectral but are non-isomorphic. The smallest pair of cospectral mates is {K1,4, C4 ∪ K1}, comprising the 5-vertex star and the graph union of the 4-vertex cycle and the single-vertex graph. The first example of cospectral graphs was reported by Collatz and Sinogowitz in 1957.