Laplacian {−1,0,1}- and {−1,1}-diagonalizable graphs

A graph is called Laplacian integral if the eigenvalues of its Laplacian matrix are all integers. We investigate the subset of these graphs whose Laplacian is furthermore diagonalized by a matrix with entries coming from a fixed set, in particular, the sets { − 1 , 0 , 1 } or { − 1 , 1 } . Such graphs include as special cases the recently-investigated families of Hadamard-diagonalizable and weakly Hadamard-diagonalizable graphs. As a combinatorial tool to aid in our investigation, we introduce a family of vectors that we call balanced , which generalizes totally balanced partitions, regular sequences, and complete partitions. We show that balanced vectors completely characterize which graph complements and complete multipartite graphs are { − 1 , 0 , 1 } -diagonalizable, and we furthermore prove results on diagonalizability of the Cartesian product, disjoint union, and join of graphs. Particular attention is paid to the { − 1 , 0 , 1 } - and { − 1 , 1 } -diagonalizability of the complete graphs and complete multipartite graphs. Finally, we provide a complete list of all simple, connected graphs on nine or fewer vertices that are { − 1 , 0 , 1 } - or { − 1 , 1 } -diagonalizable.