Spectral arbitrariness for trees fails spectacularly

Fallat, Shaun M. (author), Hall, H. Tracy (author), Levene, Rupert H. (author), Meyer, Seth A. (author), Nasserasr, Shahla (author), Oblak, Polona (author), Šmigoc, Helena (author)

Given a graph G, consider the family of real symmetric matrices with the property that the pattern of their nonzero off-diagonal entries corresponds to the edges of G. For the past 30 years a central problem has been to determine which spectra are realizable in this matrix class. Using combinatorial methods, we identify a family of graphs and multiplicity lists whose realizable spectra are highly restricted. In particular, we construct trees with multiplicity lists that require a unique spectrum, up to shifting and scaling. This represents the most extreme possible failure of spectral arbitrariness for a multiplicity list, and greatly extends all previously known instances of this phenomenon, in which only single linear constraints on the eigenvalues were observed.

• Language: English
• Keywords: spectrum, multiplicity lists, rooted trees, hedges, inverse eigenvalue problem for graphs
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: FRI - Faculty of Computer and Information Science
• Publication status: Published
• Publication version: Author Accepted Manuscript
• Year: 2024
• Number of pages: Str. 161-210
• Numbering: Vol. 169
• PID: 20.500.12556/RUL-160049
• UDC: 51
• ISSN on article: 0095-8956
• DOI: 10.1016/j.jctb.2024.06.007
• COBISS.SI-ID: 203133187
• Publication date in RUL: 12.08.2024

Record is a part of a journal

• Title: Journal of combinatorial theory
• Shortened title: J. comb. theory, Ser. B
• Publisher: Elsevier
• ISSN: 0095-8956
• COBISS.SI-ID: 25721600

Licences

• License: CC BY-NC-ND 4.0, Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
• Link: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Description: The most restrictive Creative Commons license. This only allows people to download and share the work for no commercial gain and for no other purposes.

Secondary language

• Language: Slovenian
• Keywords: spekter, seznam večkratnosti, drevo s korenom, inverzni problem lastnih vrednosti za graf