Abstract A conference matrix of order n is an $$n\times n$$ n × n matrix C with diagonal entries 0 and off-diagonal entries $$\pm 1$$ ± 1 satisfying $$CC^\top =(n-1)I$$ C C ⊤ = ( n - 1 ) I . If C is symmetric, then C has a symmetric spectrum $$\Sigma $$ Σ (that is, $$\Sigma =-\Sigma $$ Σ = - Σ ) and eigenvalues $$\pm \sqrt{n-1}$$ ± n - 1 . We show that many principal submatrices of C also have symmetric spectrum, which leads to examples of Seidel matrices of graphs (or, equivalently, adjacency matrices of complete signed graphs) with a symmetric spectrum. In addition, we show that some Seidel matrices with symmetric spectrum can be characterized by this construction.

Properties of graphs that can be characterized by the spectrum of the adjacency matrix of the graph have been studied systematically recently. Motivated by the complexity of these properties, we show that there are such properties for which testing whether a graph has that property can be NP-hard (or belong to other computational complexity classes consisting of even harder problems). In addition, we discuss a possible spectral characterization of some well-known NP-hard properties. In particular, for every integer k≥6 we construct a pair of k-regular cospectral graphs, where one graph is Hamiltonian and the other one not.

We determine all graphs for which the adjacency matrix has at most two eigenvalues (multiplicities included) not equal to $$-2$$ , or 0, and determine which of these graphs are determined by their adjacency spectrum.

We apply Godsil–McKay switching to the symplectic graphs over $$\mathbb {F}_2$$ with at least 63 vertices and prove that the 2-rank of (the adjacency matrix of) the graph increases after switching. This shows that the switched graph is a new strongly regular graph with parameters $$(2^{2\nu }-1, 2^{2\nu -1}, 2^{2\nu -2},2^{2\nu -2})$$ and 2-rank $$2\nu +2$$ when $$\nu \ge 3$$ . For the symplectic graph on 63 vertices we investigate repeated switching by computer and find many new strongly regular graphs with the above parameters for $$\nu =3$$ with various 2-ranks. Using these results and a recursive construction method for the symplectic graph from Hadamard matrices, we obtain several graphs with the above parameters, but different 2-ranks for every $$\nu \ge 3$$ .

The present issue of Designs, Codes and Cryptography is devoted to the theme "Geometric and Algebraic Combinatorics".A central concept in this research area is the Association Scheme.On one hand it can be a tool for a better understanding of combinatorial objects, such as error correcting codes, block designs, point-line incidence geometries, and permutation groups.On the other hand, many association schemes are interesting objects in themselves.This includes the strongly regular and distance-regular graphs.Algebraic tools like eigenvalues are extremely important for studying association schemes, but are also useful tools in their own right for studying the structure of graphs.Also incidence geometries, especially projective and affine geometries over finite fields are often related to association schemes, but as expected, here geometric methods play a more important role.The issue contains fourteen articles, which we'll briefly review.

We look for the maximum order m(r) of the adjacency matrix A of a graph G with a fixed rank r, provided A has no repeated rows or all-zero row. Akbari, Cameron and Khosrovshahi conjecture that m(r) = 2(r+2)/2 − 2 if r is even, and m(r) = 5 · 2(r−3)/2 − 2 if r is odd. We prove the conjecture and characterize G in the case that G contains an induced subgraph $${\frac{r}{2}K_2}$$ or $${\frac{r-3}{2}K_2+K_3}$$ .

We give some necessary conditions for a graph to be 3-chromatic in terms of the spectrum of the adjacency matrix. For all known distance-regular graphs it is determined whether they are 3-chromatic. A start is made with the classification of 3-chromatic distance-regular graphs, and it is shown that such graphs, if not complete 3-partite, must have λ ≤ 1.

The answers to several problems of Lov\hat{a}sz concerning the Shannon capacity of a graph are shown to be negative.