The inverse eigenvalue problem of a graph: multiplicities and minors

DOI10.1016/J.JCTB.2019.10.005MaRDI QIDQ1985452zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 7 April 2020

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1708.00064

zbMATH Keywords

Colin de Verdière type parameterdistinct eigenvaluesinverse eigenvalue problemmaximum multiplicitystrong Arnold propertystrong multiplicity propertystrong spectral property

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph minors (05C83) Eigenvalues, singular values, and eigenvectors (15A18) Inverse problems in linear algebra (15A29)

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 [8]. 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.

Recommendations

• The inverse eigenvalue problem of a graph
• The inverse eigenvalue and inertia problems for minimum rank two graphs
• Spectral graph theory and the inverse eigenvalue problem of a graph
• Spectral graph theory and the inverse eigenvalue problem of a graph
• Achievable multiplicity partitions in the inverse eigenvalue problem of a graph
• The combinatorial inverse eigenvalue problems: complete graphs and small graphs with strict inequality
• The eigenvalue problem of the multicyclic graph
• On the inverse eigenvalue problem for block graphs
• The combinatorial inverse eigenvalue problem. II: All cases for small graphs
• Inverse eigenvalue problems on directed graphs

Cites work

• A variant on the graph parameters of Colin de Verdiere: Implications to the minimum rank of graphs
• Computation of minimal rank and path cover number for certain graphs
• Generalizations of the strong Arnold property and the minimum number of distinct eigenvalues of a graph
• scientific article; zbMATH DE number 4055149 (Why is no real title available?)
• scientific article; zbMATH DE number 1303522 (Why is no real title available?)
• Implicit Functions and Solution Mappings
• Inverse eigenvalue problems and lists of multiplicities of eigenvalues for matrices whose graph is a tree: The case of generalized stars and double generalized stars.
• Minimum number of distinct eigenvalues of graphs
• Minimum rank and maximum eigenvalue multiplicity of symmetric tree sign patterns
• On some inverse problems in matrix theory
• On the construction of a Jacobi matrix from spectral data
• On the Eigenvalues and Eigenvectors of a Class of Matrices
• On the eigenvalues of generalized and double generalized stars
• On two conjectures regarding an inverse eigenvalue problem for acyclic symmetric matrices
• Spectral (isotropic) manifolds and their dimension
• Spectral multiplicity and splitting results for a class of qualitative matrices
• The combinatorial inverse eigenvalue problem. II: All cases for small graphs
• The implicit function theorem. History, theory, and applications
• The minimum rank of symmetric matrices described by a graph: a survey
• The Parter--Wiener Theorem: Refinement and Generalization
• Zero forcing parameters and minimum rank problems
• Zero forcing sets and the minimum rank of graphs

Cited in

(33)

• A Nordhaus-Gaddum conjecture for the minimum number of distinct eigenvalues of a graph
• A zero forcing technique for bounding sums of eigenvalue multiplicities
• Sign patterns of orthogonal matrices and the strong inner product property
• The bifurcation lemma for strong properties in the inverse eigenvalue problem of a graph
• The strong spectral property for graphs
• A geometric Gauss-Newton method for least squares inverse eigenvalue problems
• Corrigendum to: ``Achievable multiplicity partitions in the inverse eigenvalue problem of a graph
• On the inverse eigenvalue problem for block graphs
• Achievable multiplicity partitions in the inverse eigenvalue problem of a graph
• Graphs that allow all the eigenvalue multiplicities to be even
• On the inverse eigenvalue problems: the case of superstars
• Spectral graph theory and the inverse eigenvalue problem of a graph
• Spectral graph theory and the inverse eigenvalue problem of a graph
• Tight frame graphs arising as line graphs
• Ordered multiplicity inverse eigenvalue problem for graphs on six vertices
• scientific article; zbMATH DE number 7640506 (Why is no real title available?)
• Riemannian Newton-CG methods for constructing a positive doubly stochastic matrix from spectral data
• The inverse eigenvalue problem of a graph
• The combinatorial inverse eigenvalue problem. II: All cases for small graphs
• The combinatorial inverse eigenvalue problems: complete graphs and small graphs with strict inequality
• Regular graphs of degree at most four that allow two distinct eigenvalues
• The strong spectral property of graphs: graph operations and barbell partitions
• The liberation set in the inverse eigenvalue problem of a graph
• Diminimal families of arbitrary diameter
• Sparks of symmetric matrices and their graphs
• Distinct eigenvalues are realizable with generic eigenvectors
• The inverse nullity pair problem and the strong nullity interlacing property
• Spectral arbitrariness for trees fails spectacularly
• Graphs with bipartite complement that admit two distinct eigenvalues
• On the minimum number of eigenvalues of trees of diameter seven
• Inverse eigenvalue problem for discrete Schrödinger operators of a graph
• Graph products that allow two distinct eigenvalues
• A combinatorial bound on the number of distinct eigenvalues of a graph

This page was built for publication: The inverse eigenvalue problem of a graph: multiplicities and minors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1985452)