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.
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.
For a graph G, we associate a family of real symmetric matrices, S(G), where for any A∈S(G), the location of the nonzero off-diagonal entries of A are governed by the adjacency structure of G. Let ...q(G) be the minimum number of distinct eigenvalues over all matrices in S(G). In this work, we give a characterization of all connected threshold graphs G with q(G)=2. Moreover, we study the values of q(G) for connected threshold graphs with trace 2, 3, n−2, n−3, where n is the order of threshold graph. The values of q(G) are determined for all connected threshold graphs with 7 and 8 vertices with two exceptions. Finally, a sharp upper bound for q(G) over all connected threshold graph G is given.
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.
For a given graph $G$ and an associated class of real symmetric matrices whose diagonal entries are governed by the adjacencies in $G$, the collection of all possible spectra for such matrices is ...considered. Building on the pioneering work of Colin de Verdière in connection with the Strong Arnold Property, two extensions are devised that target a better understanding of all possible spectra and their associated multiplicities. These new properties are referred to as the Strong Spectral Property and the Strong Multiplicity Property. Finally, these ideas are applied to the minimum number of distinct eigenvalues associated with $G$, denoted by $q(G)$. The graphs for which $q(G)$ is at least the number of vertices of $G$ less one are characterized.
The strong spectral property for graphs Lin, Jephian C.-H.; Oblak, Polona; Šmigoc, Helena
Linear algebra and its applications,
08/2020, Volume:
598
Journal Article
Peer reviewed
Open access
We introduce the set GSSP of all simple graphs G with the property that each symmetric matrix corresponding to a graph G∈GSSP has the strong spectral property. We find several families of graphs in ...GSSP and, in particular, characterise the trees in GSSP.
The utility of a matrix satisfying the Strong Spectral Property has been well established particularly in connection with the inverse eigenvalue problem for graphs. More recently the class of graphs ...in which all associated symmetric matrices possess the Strong Spectral Property (denoted
G
SSP
) were studied, and along these lines we aim to study properties of graphs that exhibit a so-called barbell partition. Such a partition is a known impediment to membership in the class
G
SSP
. In particular we consider the existence of barbell partitions under various standard and useful graph operations. We do so by considering both the preservation of an already present barbell partition after performing said graph operations as well as barbell partitions which are introduced under certain graph operations. The specific graph operations we consider are the addition and removal of vertices and edges, the duplication of vertices, as well as the Cartesian products, tensor products, strong products, corona products, joins, and vertex sums of two graphs. We also identify a correspondence between barbell partitions and graph substructures called forts, using this correspondence to further connect the study of zero forcing and the Strong Spectral Property.
PDF
