Search

Motivated by applications in matrix constructions used in the inverse eigenvalue problem for graphs, we study a concept of genericity for eigenvectors associated with a given spectrum and a connected graph. This concept generalizes the established notion of a nowhere-zero eigenbasis. Given any simple graph G on n vertices and any spectrum with no multiple eigenvalues, we show that the family of eigenbases for symmetric matrices with this graph and spectrum is generic, strengthening a result of Monfared and Shader. We illustrate applications of this result by constructing new achievable ordered multiplicity lists for partial joins of graphs and providing several families of joins of graphs that are realizable by a matrix with only two distinct eigenvalues. [ABSTRACT FROM AUTHOR]

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]

We introduce a notion of compatibility for multiplicity matrices. This gives rise to a necessary condition for the join of two (possibly disconnected) graphs G and H to be the pattern of an orthogonal symmetric matrix, or equivalently, for the minimum number of distinct eigenvalues q of G ∨ H to be equal to two. Under additional hypotheses, we show that this necessary condition is also sufficient. As an application, we prove that q (G ∨ H) is either two or three when G and H are unions of complete graphs, and we characterise when each case occurs. [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]

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]

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

An important facet of the inverse eigenvalue problem for graphs is to determine the minimum number of distinct eigenvalues of a particular graph. We resolve this question for the join of a connected graph with a path. We then focus on bordering a matrix and attempt to control the change in the number of distinct eigenvalues induced by this operation. By applying bordering techniques to the join of graphs, we obtain numerous results on the nature of the minimum number of distinct eigenvalues as vertices are joined to a fixed graph. [ABSTRACT FROM AUTHOR]