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.