Repeated eigenvalues of the line graph of a tree and of its deck

Abstract

For a graph G on vertices v1, v2,..., vn, the p-deck of G consists of n cards each showing the characteristic polynomial φ(G-vi) of the adjacency matrix of a vertex-deleted subgraph G-vi, i = 1,2,..., n. Equivalently, a card shows the roots of G-vi, which are the eigenvalues of the adjacency matrix of G - v i. We determine certain structural features of a line graph L T of a tree T that indicate the repetition of particular eigenvalues on at least one card of the p-deck. The occurrence of repeated eigenvalues enables a constructive solution to the polynomial reconstruction problem. It is shown that the p-deck of the line graph of a tree LT, LT ≠ K3, with at least one terminal clique Kr, r > 2, contains a card with repeated eigenvalues. For exactly one terminal clique, K3, with the rest being K2s, (-1) or the pair ±√5-1/2 are the repeated eigenvalues that appear in the p-deck. The remaining line graphs of trees have only K2s as terminal cliques. The singular ones among these have a card with the eigenvalue zero repeated.