Near threshold graphs (Q1028819)

Summary: 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.