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

Abstract

Among all simple graphs on n vertices and e edges, which ones have the largest 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, 1990] showed that for given n and e there exists exactly one graph of the form G1(p,q,r) = Kp + (Sq ∪ K1,r) and exactly one G2(p,q,r) = and that one of them is optimal, where K and S indicate complete and edgeless graphs, K1,r indicates a star on r + 1 vertices, ∪ indicates disjoint union, and + indicates complete disjoint join. We specify a general threshold graph in the form G(a,b,c,d, …) = Ka + (Sb ∪ (Kc + (Sd ∪ ···))) or its complement G(a,b,c,d, …), and we prove that every optimal graph has the form G(a,b,c,d) or G(a,b,c,d) with b ⩽ 1 or c ⩽ 1 or d ⩽ 1. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 283–295, 1999