Graph Theory Problems
Inverse Spectral Problems for Graphs
Structured symmetric matrices arise in many applications in science and
engineering and their eigenvalues are of intense interest. The structure of a
symmetric matrix is conveniently encoded by means of an associated graph. For an
undirected graph G on n vertices, let S(G) be the set of all real symmetric n‐by‐n
matrices whose nonzero off‐diagonal entries occur in exactly the positions
corresponding to the edges of G. The inverse eigenvalue problem for graphs asks:
Given a graph G on n vertices and n given real numbers (with repetition allowed), is
there a matrix in S(G) with eigenvalues equal to the n given numbers. This problem
is important in understanding how the eigenvalues of a symmetric matrix are
related to its off‐diagonal zero/nonzero structure. However, for arbitrary graphs,
the inverse eigenvalue problem is very difficult.
A more modest goal is to ask: What is the maximum multiplicity M(G) of an
eigenvalue of a matrix in S(G)? This problem has been intensively studied, and
much is known. As one example, undergraduate students recently contributed to a
new result in this area: M(G) does not change when an edge in G incident to a vertex
of degree 1 or degree 2 is subdivided.
A problem whose level of difficulty lies between the inverse eigenvalue problem and
the maximum multiplicity problem for graphs is the inverse inertia problem, which
asks: Given a graph G on n vertices and a pair of nonnegative integers (p,q) with p +
q between 0 and n, is there a matrix A in S(G) that has p positive eigenvalues and q
negative eigenvalues. This problem has been completely solved for trees, but little
is known for general graphs.
Some of the questions we will consider are:
1. Suppose e = vw is an edge in a graph G for which deg(v) and deg(w) are greater
than or equal to 3 and that H is the graph obtained from G by subdividing e. When is
M(H)=M(G)?
2. Find conditions on a graph G in order that M(G) be equal to a graph theoretic
parameter Z(G) called the zero forcing number.
3. The inverse inertia problem for connected graphs that are not trees.
top |
