Near Threshold Graphs - Kirkland, Steve (The Electronic Journal of Combinatorics, 2009)
A conjecture of Grone and Merris states that for any graph G, its Laplacian spectrum, Λ(G), is majorized by its conjugate degree sequence, D^*(G). That conjecture prompts an investigation of the relationship between Λ(G) and D^*(G), and Merris has characterized the graphs G for which the multisets Λ(G) and D^*(G) are equal. In this paper, we provide a constructive characterization of the graphs G for which Λ(G) and D^*(G) share all but two elements.