Kragujevac J. Math. 25 (2003) 31-49.

SHARP BOUNDS FOR THE SUM OF THE SQUARES OF THE DEGREES OF A GRAPH

Kinkar Ch. Das

Department of Mathematics, Indian Institute of Technology,
Kharagpur 721302, W.B., India

e-mail: kinkar@mailcity.com ; kinkar@maths.iitkgp.ernet.in

(Received August 28, 2003)

Abstract. Let G=(V,E) be a simple graph with n vertices, e edges, and vertex degrees d1,d2,¼,dn. Let d1, dn be the highest and the lowest degree of vertices of G and mi be the average of the degrees of the vertices adjacent to vi Î V. We prove that

if and only if G is a star graph or a complete graph or a complete graph with one isolated vertex. We establish the following upper bound for the sum of the squares of the degrees of a graph G:

with equality if and only if G is a star graph or a complete graph or a graph of isolated vertices. Moreover, we present several upper and lower bounds for åni=1d2i and determine the extremal graphs which achieve the bounds and apply the inequalities to obtain bounds on the total number of triangles in a graph and its complement.