Diagonalization of generalized lollipop graphs

Let G be a graph formed by connecting a tree and a threshold graph with an edge between their respective roots. Let A be the adjacency matrix of G and x∈R. We give an O(n) algorithm for constructing a diagonal matrix D congruent to A+xIn, allowing us to locate eigenvalues of A and obtain spectral results.