Laplacian \-1,0,1\- and \-1,1\-diagonalizable graphs

DOI10.1016/J.LAA.2024.10.016MaRDI QIDQ6640934zbMATH OpenFDO

Authors Nathaniel Johnston, Sarah Plosker

Publication date 20 November 2024

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.LAA.2024.10.016

zbMATH Keywords

eigenspacesHadamard diagonalizable graphsHadamard matricesLaplacian integral graphs

Mathematics Subject Classification ID

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Structural characterization of families of graphs (05C75) Graph operations (line graphs, products, etc.) (05C76) Eigenvalues, singular values, and eigenvectors (15A18)

Review text

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.

Recommendations

• On Hadamard diagonalizable graphs
• Hadamard diagonalizable graphs of order at most 36
• Weakly Hadamard diagonalizable graphs
• The Laplacian polynomial of complete multipartite graphs
• On graph Laplacian eigenvectors with components in \(\{- 1, 0, 1 \}\)

Cites work

• \(\{-1,0,1\}\)-basis for the null space of a forest
• Complex Hadamard diagonalisable graphs
• Constructably Laplacian integral graphs
• Hadamard diagonalizable graphs of order at most 36
• scientific article; zbMATH DE number 4111676 (Why is no real title available?)
• scientific article; zbMATH DE number 1391684 (Why is no real title available?)
• Indecomposable Laplacian integral graphs
• Laplacian graph eigenvectors
• On certain eigenspaces of cographs
• On Hadamard diagonalizable graphs
• Perfect quantum state transfer using Hadamard diagonalizable graphs
• Perfect state transfer in Laplacian quantum walk
• The Laplacian polynomial of complete multipartite graphs
• The Laplacian Spectrum of a Graph II
• The Rank of Circulant Matrices
• Van Lier sequences
• Weakly Hadamard diagonalizable graphs

Cited in

(1)

• Weakly Hadamard diagonalizable graphs and quantum state transfer

This page was built for publication: Laplacian \(\{-1,0,1\}\)- and \(\{-1,1\}\)-diagonalizable graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6640934)