\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf Steve Kirkland}
%
%
\medskip
\noindent
%
%
{\bf Near Threshold Graphs}
%
%
\vskip 5mm
\noindent
%
%
%
%
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.

\bye