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.
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.
We propose a Nordhaus–Gaddum conjecture for q(G), the minimum number of distinct eigenvalues of a symmetric matrix corresponding to a graph G: for every graph G excluding four exceptions, we ...conjecture that q(G)+q(Gc)≤|G|+2, where Gc is the complement of G. We compute q(Gc) for all trees and all graphs G with q(G)=|G|−1, and hence we verify the conjecture for trees, unicyclic graphs, graphs with q(G)≤4, and for graphs with |G|≤7.
A hollow matrix described by a graph $G$ is a real symmetric matrix having all diagonal entries equal to zero and with the off-diagonal entries governed by the adjacencies in $G$. For a given graph ...$G$, the determination of all possible spectra of matrices associated with $G$ is the hollow inverse eigenvalue problem for $G$. Solutions to the hollow inverse eigenvalue problems for paths and complete bipartite graphs are presented. Results for related subproblems such as possible ordered multiplicity lists, maximum multiplicity of an eigenvalue, and minimum number of distinct eigenvalues are presented for additional families of graphs.
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.
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.
PDF
