The inverse eigenvalue problem of a graph: Multiplicities and minors

Date
2020-05-01
Authors
Barrett, Wayne
Butler, Steve
Fallat, Shaun
Hall, H. Tracy
Hogben, Leslie
Lin, Jephian
Shader, Bryan
Young, Michael
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Authors
Research Projects
Organizational Units
Mathematics
Organizational Unit
Journal Issue
Series
Abstract

The inverse eigenvalue problem of a given graph G is to determine all possible spectra of real symmetric matrices whose off-diagonal entries are governed by the adjacencies in G. Barrett et al. introduced the Strong Spectral Property (SSP) and the Strong Multiplicity Property (SMP) in [Generalizations of the Strong Arnold Property and the minimum number of distinct eigenvalues of a graph. Electron. J. Combin., 2017]. In that paper it was shown that if a graph has a matrix with the SSP (or the SMP) then a supergraph has a matrix with the same spectrum (or ordered multiplicity list) augmented with simple eigenvalues if necessary, that is, subgraph monotonicity. In this paper we extend this to a form of minor monotonicity, with restrictions on where the new eigenvalues appear. These ideas are applied to solve the inverse eigenvalue problem for all graphs of order five, and to characterize forbidden minors of graphs having at most one multiple eigenvalue.

Description

This is a manuscript of an article published as Barrett, Wayne, Steve Butler, Shaun M. Fallat, H. Tracy Hall, Leslie Hogben, Jephian C-H. Lin, Bryan L. Shader, and Michael Young. 142 "The inverse eigenvalue problem of a graph: Multiplicities and minors." Journal of Combinatorial Theory, Series B (2020): 276-306. DOI: 10.1016/j.jctb.2019.10.005. Posted with permission.

Keywords
Inverse Eigenvalue Problem, Strong Arnold Property, Strong Spectral Property, Strong Multiplicity Property, Colin de Verdière type parameter, Maximum multiplicity, Distinct eigenvalues
Citation
DOI
Collections