Spectra of Graphs

In Spring 2006, Andries E. Brouwer and Willem H. Haemers gave a series of lectures at IPM, the Institute for Studies in Theoretical Physics and Mathematics in Tehran. The lecture notes were combined and published as an IPM report. Since that time, various versions of that text have been available at this site.

Preprint PDF.

A book version was released by Springer on the 16th of December 2011. However, the copyright year is 2012.

A.E. Brouwer & W.H. Haemers, Spectra of graphs, Springer, New York, etc., 2012.
ISBN 978-1-4614-1938-9.

Book Errata

p. 39, in the proof of Theorem 3.5.1, ‘θn−α−1’ should be ‘θn−α+1’.

p. 40, Proposition 3.6.3: add in part (ii) the condition ‘θm ≥ 0’, and in part (iii) the condition ‘θt+m−1 ≥ 0’.

p. 55, 3rd line following Step 4: semibipartite should be split.

p. 87, Proposition 5.3.2, 2nd line: replace eigenvalue by eigenvector.

p. 93, line 9: replace edge-transitive by arc-transitive.

p. 119, Proposition 9.1.4: add the word ‘primitive’: A primitive strongly regular graph ....

p. 117, 151 replace in the definition of ‘restricted eigenvalue’ the part perpendicular to by which is not a multiple of.

p. 138, line 13, ‘f : F→K’ should be ‘f : K→F’.

p. 140, lines 13, 18: replace ‘qk−2’ and ‘qk’ by ‘qm−2’ and ‘qm’.

p. 160, bottom line, replace ‘(196,±1)’ by ‘(196,1)’.

p. 161, line 2: add in (iii) the condition ‘4|a’.

p. 166: in (iv) replace ‘i,j,k’ by ‘i,j’.

p. 167: in the line before Theorem 11.2.1, replace ‘Ek’ by ‘Ei’.

p. 167, Theorem 11.2.2: replace ‘For i’ by ‘For j’.

p. 169: in the line before Theorem 11.3.2, replace ‘b × (d+1)’ by ‘n × (d+1)’.

p. 205, bottom line, instead of ‘n=6’, read ‘n=4’.


On p. 37, line 2 a conjecture (by Nikiforov) on the sum of the spectral radii of a graph and its complement is mentioned. This conjecture has now been proved by Tamás Terpai.

On p. 210 it says: One might wonder whether the disjoint union of regular DS graphs with the same degree is always DS. Wonder no more! Both 2K3,3 + Σ ⊗ K2 and 3(C6 □ K2) are bipartite cubic graphs with spectrum ±33 ±26 ±13 012.

On p. 163 a table with bounds for the maximum number of equiangular lines in Rd is given. These bounds were taken from a survey by Seidel, but no proofs are known, and perhaps they are lower bounds only. Improved table, including recent results of Barg-Yu, Azarija-Marc, Greaves-Koolen-Munemasa-Szöllősi, Greaves and Szöllősi:

1 2 3 4 5 6 7-13 14 15 16 17 18 19 20 21 22 23-41 42 43
1 3 6 6 10 16 28 28-29 36 40-41 48-50 54-60 72-75 90-95 126 176 276 276-288 344


Thanks to Sebastian Cioabă, Nathann Cohen, Péter Csikvári, Alexander Gavrilyuk, Marko Orel, Dima Pasechnik and Ferenc Szöllősi for pointing out problems.

Valid HTML 4.01 Transitional