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

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

The energy of a graph T is the sum of the absolute values of the eigenvalues of the adjacency matrix of T. Seidel switching is an operation on the edge set of T. In some special cases Seidel switching does not change the spectrum, and therefore the energy. Here we investigate when Seidel...

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