# What is/are the best bound/s on the sum of squares of degrees in a graph?

Let $G$ be a graph with degrees $d_{1},\ldots,d_{n}$. I am interested in upper bounds on $$\sum_{i=1}^{n}{d_{i}^{2}}.$$ An example is de Caen's bound: $$\sum_{i=1}^{n}{d_{i}^{2}} \leq e(\frac{2e}{n-1}+n-2),$$ where $e$ is the number of edges. His bound is very elegant but far from tight. I have read many papers which give other bounds but now I am a bit confused and would love to know if someone can supply a definitive answer.

P.S. The quantity in question is also known as the "first Zagreb index", mostly in chemistry-related circles.

• This was address in the TCS question, "Bounds on sum of squares of node degrees in undirected graphs," where David Eppstein's answer may be of some help. – Joseph O'Rourke Feb 21 '14 at 13:16
• A quick search yields the paper New sharp bounds on the first Zagreb index, where they show that for connected graphs $G=(V,E)$, $$M_1(G) \leq e(e+1)$$ $$M_1(G) \leq n(2n-e+1)$$which are each sharp for some graphs. Cauchy-Schwarz yields the lower bound $$4e^2/n\leq M_1(G).$$ We are essentially trying to bound the second moment of a function $d:V\rightarrow \mathbb{N}$ by the first moment and the size of the domain $V$, so any simple bounds will not be tight in every case. – Eric Naslund Feb 21 '14 at 13:37

There is a simple spectral upper bound: namely, denoting by $A$ the adjacency matrix of $G$, and by $\mathbf 1$ the $n$-dimensional all-$1$ vector, we have $$\sum_{I=1}^n d_i^2=\|A{\mathbf 1}\|^2 \le \|A\|^2 \|{\mathbf 1}\|^2 = n\lambda_{\rm max}^2,$$ where $\lambda_{\rm max}$ is the largest eigenvalue of $G$. This bound is sharp, say, for regular graphs.