Reconstruction of weighted graphs by their spectrum (Q1580674): Difference between revisions

A weighted graph \(G\) is a pair \((A,M)\) where \(A\) and \( M\) are two matrices with \(A_{ii}=0\) and \(M\) is real diagonal. If the mass coefficients \(m_i\) are equal to 1, then \(G\) is a simple graph. If \(m_i >0\) and \(A_{ij} \geq 0\), the weighted graph is a model for a molecule or, alternatively, a discrete model of an inhomogeneous drum. The Laplace spectrum of a weighted graph is the set of solutions of \(\text{det}(A-D-x M)=0\), where \(D\) is the valence matrix of \(A\). Many results, as the theorem of Botti and Merris, seem to indicate that it is in general impossible to reconstruct the structure of a molecule from its spectrum. The authors state that, under some condition on the mass matrix \(M\), one can compute the adjacency matrix of a graph from its Laplace spectrum. A reconstruction algorithm is provided. The sufficient conditions that allow this reconstruction are either strong growth conditions on the masses when \(A_{i,j} \in \{0,1\}\), or an algebraic condition which shows that for almost all mass matrices, reconstruction of the adjacendcy matrix \(A\) is possible.