Laplacian \(\{-1,0,1\}\)- and \(\{-1,1\}\)-diagonalizable graphs (Q6640934)

A graph is called Laplacian integral if the eigenvalues of its Laplacian matrix are all integers. Motivated by the notion of weak Hadamard diagonalizable graphs introduced by \textit{M. Adm} et al. [ibid. 610, 86--119 (2021; Zbl 1458.05136)], the authors investigate the subset of these graphs whose Laplacian matrix is diagonalized by matrices with all entries belonging to \(\{-1, 0, 1\}\) or \(\{-1, 1\}\), with or without the assumption of orthogonality or quasi-orthogonality of its columns. 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 this investigation, the authors introduce a family of vectors called balanced, which generalizes totally balanced partitions, regular sequences, and complete partitions. It is shown that balanced vectors completely characterize which graph complements and complete multipartite graphs are \(\{-1, 0, 1\}\)-diagonalizable, and furthermore results on diagonalizability of the Cartesian product, disjoint union, and join of graphs are proved. Particular attention is paid to the \(\{-1, 0, 1\}\)- and \(\{-1, 1\}\)-diagonalizability of the complete graphs and complete multipartite graphs. Finally, a complete list of all simple, connected graphs on nine or fewer vertices that are \(\{-1, 0, 1\}\)- or \(\{-1, 1\}\)-diagonalizable is provided. It is interesting to note that every single graph on 9 or fewer vertices that is \(\{-1, 0, 1\}\)-diagonalizable can be constructed using \(K_1\) via the operations and theorems described earlier in the paper, namely complementation, disjoint union, and the Cartesian product. Some open problems conclude the paper.