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. 14, in the caption of Fig. 1.2, the last eigenvalues are ½(−1±√17), that is, a minus sign was missing.

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. 57, middle: replace ‘N_i^Tt₀...t_i’ by ‘N_i+1^Tt₀...t_i’.

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. 125, line −9: replace ‘K₅’ by ‘C₅’.

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

p. 140, lines 13, 18: replace ‘q^k−2’ and ‘q^k’ by ‘q^m−2’ and ‘q^m’.

p. 155, line 9: replace ‘1’ by ‘≥1’ in the table entries for 126 and 176.

p. 158, line 16: replace ‘of the second row’ by ‘of the last n−3 elements of the second row’.

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 ‘E_k’ by ‘E_i’.

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’.

Additions

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 2K_3,3 + Σ ⊗ K₂ and 3(C₆ □ K₂) are bipartite cubic graphs with spectrum ±3³ ±2⁶ ±1³ 0¹².

On p. 163 a table with bounds for the maximum number of equiangular lines in R^d 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

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