A divisible design graph is a graph whose adjacency matrix is the incidence matrix of a divisible design. These graphs are a natural generalization of (v, k, ⋋)-graphs. In this paper we develop some theory, find many parameter conditions and give several constructions

We construct graphs that are cospectral but nonisomorphic with Kneser graphs K(n, k), when n =3k - 1, k> 2 and for infinitely many other pairs (n, k). We also prove that for 3 ≤ k ≤ n - 3 the Modulo-2 Kneser graph K2(n, k) is not determined by the spectrum

For every rational number x 2 (0; 1), we construct a pair of graphs one regular and one nonregular with adjacency matrices A1 and A2, having the property that A1-xJ and A2-xJ have the same spectrum (J is the all-ones matrix). This solves a problem of Van Dam and the second author.For some values...

Let k be a natural number and let G be a graph with at least k vertices. A.E. Brouwer conjectured that the sum of the k largest Laplacian eigenvalues of G is at most e(G) (k choose 2), where e(G) is the number of edges of G. We prove this conjecture for k = 2. We also show that if G is a tree,...

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

Let J be the all-ones matrix, and let A denote the adjacency matrix of a graph. An old result of Johnson and Newman states that if two graphs are cospectral with respect to yJ - A for two distinct values of y, then they are cospectral for all y. Here we will focus on graphs cospectral with...