(n,e)-graphs with maximum sum of squares of degrees

Among all simple graphs on n vertices and e edges, which ones have the larg est sum of squares of the vertex degrees! It is easy to see that they must be threshold graphs, but not every threshold graph is optimal in this sense . Boesch et al. [Boesch et al., Tech Rep, Stevens Inst Tech, Hoboken NJ, 19 90] showed that for given n and e there exists exactly one graph of the for m G(1), (p, q, r) = K-p + (S-q boolean OR K-1,K-r) and exactly one G(2) (p q, r) = S-p boolean OR (K-q + <(K-1,K-r)over bar>) and that one of them is optimal, where K and S indicate complete and edgeless graphs, K-1,K-r indic ates a star on r + 1 vertices, boolean OR indicates disjoint union, and + i ndicates complete disjoint join. We specify a general threshold graph in th e form G(1)*(a, b, c, d,...) = K-a + (S-b boolean OR (K-c + (S-d boolean OR ...))) Or its complement G(2)*(a, b, c, d,...), and we prove that every op timal graph has the Corm G(1)*(a, b, c, d) or G(2)*(a, b, c, d) with b less than or equal to 1 or c less than or equal to 1 or d less than or equal to 1. (C) 1999 John Wiley & Sons, Inc.