Split non-threshold Laplacian integral graphs

Abstract

The aim of this article is to answer a question posed by Merris in European Journal of Combinatorics, 24 (2003) pp. 413 − 430, about the possibility of finding split non-threshold graphs that are Laplacian integral, i.e. graphs for which the eigenvalues of the corresponding Laplacian matrix are integers. Using Kronecker products, balanced incomplete block designs, and solutions to certain Diophantine equations, we show how to build infinite families of these graphs.