Maximizing the sum of the squares of the degrees of a graph Original Research Article

Let G=(V,E) be a simple graph with n vertices, e edges, and vertex degrees d1,d2,…,dn. Also, let d1, dn be, respectively, the highest degree and the lowest degree of G and mi be the average of the degrees of the vertices adjacent to vertex vi∈V. It is proved thatmax{dj+mj : vj∈V}⩽2en−1+n−2with equality if and only if G is an Sn graph (K1,n−1⊆Sn⊆Kn) or a complete graph of order n−1 with one isolated vertex. Using the above result we establish the following upper bound for the sum of the squares of the degrees of a graph G:∑i=1n di2⩽e2en−1+n−2n−1 d1+(d1−dn) 1− d1n−1with equality if and only if G is a star graph or a regular graph or a complete graph Kd1+1 with n−d1−1 isolated vertices. A comparison is made to another upper bound on ∑i=1n di2, due to de Caen (Discrete Math. 185 (1998) 245). We also present several upper bounds for ∑i=1n di2 and determine the extremal graphs which achieve the bounds.