Finding All The Bivalent Laplacian Eigenvectors of a Graph

For a graph G=(V,E) on n vertices, the Laplacian matrix is defined as L=D-A, where D = diag[d1, ..., dn] is the n x n diagonal degree matrix and A is the (0,1)-adjacency matrix. The Laplacian is vital in spectral graph theory and physics models. Specifically, the graph wave equation Cv_tt - ∇^T L^-1 ∇v = s_t helps study analogues of continuous differential operators in discrete networks.

[Knippel et al., 2019] found that graphs whose Laplacian matrices have eigenvectors in {-1, 1}^n are particularly critical for this wave equation. We call these "bivalent graphs". Alongside their importance in physical models, they possess intriguing graph-theoretical properties.

In this work, we study bivalent graphs and their properties. Furthermore, we propose a mathematical model to determine whether a given graph G is bivalent. If it is, the model outputs all non-null eigenvalues and their corresponding bivalent eigenvectors.