GRAPHS WITH SMALLEST SUM OF SQUARES OF VERTEX DEGREES
Ivan Gutman
Faculty of Science, P. O. Box 60, 34000 Kragujevac, Serbia
and Montenegro
(Received September 2, 2003)
Abstract. Graphs with n vertices, m edges, and
with smallest sum of squares of the vertex degrees are
characterized. These are the graphs in which the degree of any
vertex is equal to either [2m/n] or [2m/n].
Such graphs exist for all n £ 1 and 0 £ m £ n(n-1)/2.