Some simple graph spectra

The (ordinary) spectrum of a graph is the spectrum of its (0,1) adjacency matrix. (There are other concepts of spectrum, like the Laplace spectrum or the Seidel spectrum, that are the spectrum of other matrices associated with the graph.)

Here we give the spectrum of some simple graphs. (No proofs, or only brief indications. Full proofs are elsewhere.)

0.1 Complete and cocomplete graphs

The graph on n vertices without edges (the n-coclique, \overline{K}_{n}) has zero adjacency matrix, hence spectrum 0^{n}, where the exponent denotes the multiplicity.

The complete graph on n vertices (the n-clique, K_{n}) has adjacency matrix A = J − I, where J is the all-1 matrix, and I is the identity matrix. Since J has spectrum n^{1}, 0^{n−1} and I has spectrum 1^{n} and IJ = JI, it follows that K_{n} has spectrum (n − 1)^{1}, (−1)^{n−1}.

Note that our graphs are undirected, so that the matrix is symmetric and the eigenvalues are real. Note that our graphs do not have loops so that the matrix has zero diagonal and hence zero trace, so that the eigenvalues sum to zero.

0.2 Regular graphs

If A is the adjacency matrix of a regular graph Γ of valency k, then each row of A has k ones, so that A1 = k1 where 1 is the all-1 vector, that is, Γ has eigenvalue k. (The multiplicity of the eigenvalue k is the number of connected components of the graph Γ.)

0.3 Complements

If A is the adjacency matrix of a graph Γ, then J − I − A is the adjacency matrix of the complementary graph \overline{Γ}. If Γ has n vertices, and is regular of valency k (so that AJ = JA = kJ) then \overline{Γ} is regular of valency n − k − 1, and the remaining n − 1 eigenvalues of \overline{Γ} are −1 − θ where θ runs through the n − 1 eigenvalues of Γ belonging to an eigenvector orthogonal to 1.

For example, the n-coclique has n eigenvalues 0, and its complement, the n-clique, has 1 eigenvalue n − 1 and n − 1 eigenvalues −1.

0.4 Complete bipartite graphs

The complete bipartite graph K_{m,n} has spectrum ±\sqrt{mn}, 0^{m+n−2}.

More generally, every bipartite graph has a spectrum that is symmetric w.r.t. the origin: if θ is eigenvalue, then also −θ, with the same multiplicity.

0.5 Cycles

Some small cycles:

cycle spectrum  comments
C_{3} 2, (−1)^{2}  this is K_{3}
C_{4} 2, 0^{2}, −2  this is K_{2,2}
C_{5} 2, (\frac{−1+\sqrt{5}}{2})^{2}, (\frac{−1−\sqrt{5}}{2})^{2} the pentagon is a srg
C_{6} 2, 1^{2}, (−1)^{2}, −2

More generally, the n-cycle C_{n} has eigenvalues

2 cos(2πj/n) (j = 0, …, n − 1).

One sees that all multiplicities are 2, except that of 2 and possibly −2.

A cycle has an adjacency matrix that is a circulant: A = (a_{ij}) where a_{ij} = a_{0,j−i} (with indices computed mod n). The circulant with top row (c_{0}, ..., c_{n−1}) has eigenvalues ∑ c_{i}ω^{i} where ω runs through the n-th roots of unity. The corresponding eigenvectors are (1, ω, ω^{2}, ..., ω^{n−1})^{⊤}. In particular one finds for the cycle eigenvalues ω + ω^{n−1} = ω + ω^{−1} = ω + \overline{ω} = 2Re ω.

0.6 Paths

Some small paths:

path spectrum  comments
P_{1} 0  this is K_{1}
P_{2} 1, −1  this is K_{2}
P_{3} \sqrt{2}, 0, −\sqrt{2} this is K_{1,2}
P_{4}  \frac{1+\sqrt{5}}{2}, \frac{−1+\sqrt{5}}{2}, \frac{1−\sqrt{5}}{2}, \frac{−1−\sqrt{5}}{2}
P_{5}  \sqrt{3}, 1, 0, −1, −\sqrt{3}

More generally, the path P_{n} has eigenvalues

2 cos(πj/(n + 1) (j = 1, …, n).

All multiplicities are 1.

One way of seeing that these are the eigenvalues, is by taking an eigenvalue of multiplicity 2 of the (2n + 2)-cycle. All eigenvectors have the property that opposite vertices have opposite values. So if one vertex has value 0 for an eigenvector, then so has the opposite one, and we find an eigenvector for the disjoint union of two paths P_{n}.

0.7 Dynkin diagrams and extended Dynkin diagrams

The Dynkin diagram A_{n} is the path P_{n}. The extended Dynkin diagram Â_{n} is the cycle C_{n+1}. For both, see above.

Some small cases:

path spectrum  comments
D_{4} \sqrt{3}, 0, 0, −\sqrt{3} this is K_{1,3}
D_{5} 0, 2 cos(πj/8), j = 1, 3, 5, 7
D_{6} 0, 2 cos(πj/10), j = 1, 3, 5, 7, 9
D_{7} 0, 2 cos(πj/12), j = 1, 3, 5, 7, 9, 11
E_{6} 2 cos(πj/12), j = 1, 4, 5, 7, 8, 11
E_{7} 2 cos(πj/18), j = 1, 5, 7, 9, 11, 13, 17
E_{8} 2 cos(πj/30), j = 1, 7, 11, 13, 17, 19, 23, 29
D̂_{4} 2, 0, 0, 0, −2  this is K_{1,4}
D̂_{5} 2, 1, 0, 0, −1, −2
D̂_{6} 2, \sqrt{2}, 0, 0, 0, \sqrt{2}, −2
D̂_{7} 2, τ, τ^{−1}, 0, 0, −τ^{−1}, −τ, −2
Ê_{6} 2, 1, 1, 0, −1, −1, −2
Ê_{7} 2, \sqrt{2}, 1, 0, 0, −1, −\sqrt{2}, −2
Ê_{8} 2, τ, 1, τ^{−1}, 0, −τ^{−1}, −1, −τ, −2

where τ = \frac{1+\sqrt{5}}{2} = 2 cos(π/5) and τ^{−1} = τ − 1.

More generally, D_{n} has eigenvalues 0 and 2 cos(πj/(2n−2)), j = 1, 3, 5, …, 2n− 3. And D̂_{n} has eigenvalues 2, 0, 0, −2 and 2 cos(πj/(n − 2)) j = 1, …, n − 3. (An easy argument is found by pasting two copies together to obtain a path P_{2n−3} or cycle C_{2n−4}.)

The eigenvalues of the Dynkin diagrams are 2 cos((d_{i}−1)π/h) (1 ≤ i ≤ n) where h is the Coxeter number, and the d_{i} are the degrees. In all cases the largest eigenvalue is 2 cos(π/h).

0.8 Cospectral graphs

It is not true that a graph is uniquely determined by its spectrum. It is easy to construct counterexamples from the above by taking disjoint unions. For example, K_{1,4} and the disjoint union C_{4} + K_{1} both have spectrum 2, 0, 0, 0, −2. And Ê_{6} and C_{6} + K_{1} both have spectrum 2, 1, 1, 0, −1, −1, −2. And D̂_{7} + K_{2} and Ê_{8} + K_{1} both have spectrum 2, τ, 1, τ^{−1}, 0, 0, −τ^{−1}, −1, −τ, −2.

But many properties of a graph can be recognized from the spectrum. As a first example, the number of edges is half the trace of A^{2}, that is, is \frac{1}{2} ∑ θ^{2}.

It is an open problem whether most graphs are uniquely determined by their spectrum.

0.9 Cubes

The n-cube graph (called 2^{n}, or Q_{n}) is the graph with as vertices the binary vectors of length n, where two vectors are adjacent when they differ in a single position. The 0-cube is K_{1}, the 1-cube is K_{2}, the 2-cube is C_{4}.

The spectrum of 2^{n} consists of the eigenvalues n − 2i with multiplicity \binom{n}{i} (0 ≤ i ≤ n).

More generally, if Γ and Δ are graphs with eigenvalues θ_{i} and η_{j}, respectively, then their Cartesian product Γ × Δ has eigenvalues θ_{i} + η_{j}.

0.10 Strongly regular graphs

A strongly regular graph (srg) with parameters (v, k, λ, μ) is a graph on v vertices, regular of valency k, such that any two adjacent (nonadjacent) vertices have precisely λ (resp. μ) common neighbours.

For example, the pentagon is a strongly regular graph with parameters (5, 2, 0, 1), and the Petersen graph is one with parameters (10, 3, 0, 1).

One excludes complete or cocomplete graphs (where μ resp. λ is not welldefined).

The parameter condition is equivalent to the matrix equation A^{2} = kI + λA + μ(J − I − A) and AJ = JA = kJ.

0.10.1 Spectrum

The spectrum consists of three eigenvalues k, r, s, where r ≥ 0 > s and r, s are the solutions of x^{2} + (μ − λ)x + μ − k = 0.

These three eigenvalues have multiplicities 1, f, g, respectively, found from 1 + f + g = v and k + fr + gs = tr A = 0.

Clearly, these multiplicities are nonnegative integers, and that is a strong condition on the parameters. If f ≠ g then one can solve r, s from r + s = λ − μ and k + fr + gs = 0 and finds that the algebraic integers r, s are rational. It follows that in this case all eigenvalues are integers.

If f = g then we are in the ‘half case’: for some nonnegative integer t one has (v, k, λ, μ) = (4t + 1, 2t, t − 1, t). Now f = g = 2t and r, s = (−1 ± \sqrt{v})/2. Examples are the Paley graphs: the elements of the finite field GF (q) where q = 4t + 1, adjacent when the difference is a nonzero square.

0.10.2 Imprimitive cases

Trivial examples are the unions of complete graphs and their complements, the complete multipartite graphs.

The union aK_{m} of a copies of K_{m} (where a, m > 1) has parameters (v, k, λ, μ) = (am, m − 1, m − 2, 0) and spectrum k^{a}, (−1)^{a(m−1)}. We have r = k here. Conversely, if r = k (or if μ = 0) then we are in this case.

The complete a-partite graph K_{a×m}, complement of the previous, has parameters (v, k, λ, μ) = (am, (a − 1)m, (a − 2)m, (a − 1)m) and spectrum k^{1}, 0^{a(m−1)}, (−m)^{a−1}. Conversely, if r = 0 (or if μ = k) then we are in this case.