Reconstruction of weighted graphs by their spectrum (Q1580674): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2018886572 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Almost all trees share a complete set of immanantal polynomials / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5691133 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The Laplacian Spectrum of a Graph II / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The Laplacian Spectrum of a Graph / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Generation of isospectral graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4323294 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Sufficient Condition for All the Roots of a Polynomial To Be Real / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4189313 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5620774 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4696392 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5676231 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Generalized Matrix Functions and the Graph Isomorphism Problem / rank | |||
Normal rank |
Latest revision as of 16:05, 30 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Reconstruction of weighted graphs by their spectrum |
scientific article |
Statements
Reconstruction of weighted graphs by their spectrum (English)
0 references
8 July 2001
0 references
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.
0 references
weighted graph
0 references
Laplace spectrum
0 references
reconstruction
0 references