Near Threshold Graphs

Abstract

A conjecture of Grone and Merris states that for any graph $G$, its Laplacian spectrum, $\Lambda(G)$, is majorized by its conjugate degree sequence, $D^*(G)$. That conjecture prompts an investigation of the relationship between $\Lambda(G)$ and $D^*(G),$ and Merris has characterized the graphs $G$ for which the multisets $\Lambda(G)$ and $D^*(G)$ are equal. In this paper, we provide a constructive characterization of the graphs $G$ for which $\Lambda(G)$ and $D^*(G)$ share all but two elements.