Search

The inverse eigenvalue problem of a graph G is the problem of characterizing all lists of eigenvalues of real symmetric matrices whose off-diagonal pattern is prescribed by the adjacencies of G. The strong spectral property is a powerful tool in this problem, which identifies matrices whose entries can be perturbed while controlling the pattern and preserving the eigenvalues. The Matrix Liberation Lemma introduced by Barrett et al. in 2020 advances the notion to a more general setting. In this paper we revisit the Matrix Liberation Lemma and prove an equivalent statement, that reduces some of the technical difficulties in applying the result. We test our method on matrices of the form M = A ⊕ B and show how this new approach supplements the results that can be obtained from the strong spectral property only. While extending this notion to the direct sums of graphs, we discover a surprising connection with the zero forcing game on Cartesian products of graphs. Throughout the paper we apply our results to resolve a selection of open cases for the inverse eigenvalue problem of a graph on six vertices. [ABSTRACT FROM AUTHOR]

In this work, the inverse eigenvalue problem is completely solved for a subfamily of clique-path graphs, in particular for lollipop graphs and generalized barbell graphs. For a matrix A with associated graph G , a new technique utilizing the strong spectral property is introduced, allowing us to construct a matrix A ′ whose graph is obtained from G by appending a clique while arbitrary list of eigenvalues is added to the spectrum. Consequently, many spectra are shown realizable for block graphs. [ABSTRACT FROM AUTHOR]

Given a graph G , one may ask: "What sets of eigenvalues are possible over all weighted adjacency matrices of G ?" (The weight of an edge is positive or negative, while the diagonal entries can be any real numbers.) This is known as the Inverse Eigenvalue Problem for graphs (IEPG). A mild relaxation of this question considers the multiplicity list instead of the exact eigenvalues themselves. That is, given a graph G on n vertices and an ordered partition m = (m 1 , ... , m ℓ) of n , is there a weighted adjacency matrix where the i -th distinct eigenvalue has multiplicity m i ? This is known as the ordered multiplicity IEPG. Recent work solved the ordered multiplicity IEPG for all graphs on 6 vertices. In this work, we develop zero forcing methods for the ordered multiplicity IEPG in a multitude of different contexts. Namely, we utilize zero forcing parameters on powers of graphs to achieve bounds on consecutive multiplicities. We are able to provide general bounds on sums of multiplicities of eigenvalues for graphs. This includes new bounds on the sums of multiplicities of consecutive eigenvalues as well as more specific bounds for trees. Using these results, we verify the previous results above regarding the IEPG on six vertices. In addition, applying our techniques to skew-symmetric matrices, we are able to determine all possible ordered multiplicity lists for skew-symmetric matrices for connected graphs on five vertices. [ABSTRACT FROM AUTHOR]

We introduce the set G SSP of all simple graphs G with the property that each symmetric matrix corresponding to a graph G ∈ G SSP has the strong spectral property. We find several families of graphs in G SSP and, in particular, characterise the trees in G SSP. [ABSTRACT FROM AUTHOR]

The inverse eigenvalue problem studies the possible spectra among matrices whose off-diagonal entries have their zero-nonzero patterns described by the adjacency of a graph G. In this paper, we refer to the i -nullity pair of a matrix A as (null (A) , null (A (i)) , where A (i) is the matrix obtained from A by removing the i -th row and column. The inverse i -nullity pair problem is considered for complete graphs, cycles, and trees. The strong nullity interlacing property is introduced, and the corresponding supergraph lemma and decontraction lemma are developed as new tools for constructing matrices with a given nullity pair. [ABSTRACT FROM AUTHOR]

Given a graph G with vertices { v 1 , ... , v n } , we define S (G) to be the set of symmetric matrices A = [ a i , j ] such that for i ≠ j we have a i , j ≠ 0 if and only if v i v j ∈ E (G). Motivated by the Graph Complement Conjecture, we say that a graph G is complementary vanishing if there exist matrices A ∈ S (G) and B ∈ S (G ‾) such that A B = O. We provide combinatorial conditions for when a graph is or is not complementary vanishing, and we characterize which graphs are complementary vanishing in terms of certain minimal complementary vanishing graphs. In addition to this, we determine which graphs on at most 8 vertices are complementary vanishing. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]