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

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

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

Using results on Hadamard difference sets, we construct regular graphical Hadamard matrices of negative type of order 4m^4 for every positive integer m. If m is greater than 1, such a Hadamard matrix is equivalent to a strongly regular graph with parameters (4m^4, 2m^4 + m^2, m^4 + m^2, m^4 +...

Consider a graph Ґ on n vertices with adjacency matrix A and degree sequence (d1, . . . , dn). A universal adjacency matrix of Ґ is any matrix in Span {A,D, I, J} with a nonzero coefficient for A, where D = diag (d1, . . . , dn) and I and J are the n × n identity and all-ones matrix,...

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