Near Threshold Graphs

摘要

A conjecture of Grone and Merris states that for any graph G, its Laplacianspectrum, A(G), is majorized by its conjugate degree sequence, D~* (G). That con-jecture prompts an investigation of the relationship between A(G) and D~* (G),andMerris has characterized the graphs G for which the multisets A(G) and D~* (G)areequal. In this paper, we provide a constructive characterization of the graphs G forwhich A(G) and D~* (G)share all but two elements.