Bounds on sum of squares of node degrees in undirected graphs

Question

Admittedly, this is less of a research-y question (and admittedly, a little non-algorithmic trivial question), but I am hoping to get some meaningful answer.

Given an undirected graph $G = (V, E)$, with $n = |V|$ vertices and $m = |E|$ edges, what is a good upper bound on $\sum_{v \in V} \deg^2(v)$ in terms of $m$ and $n$.

Two obvious upper bounds are $O(n^3)$ and $O(m^2)$, which are quite weak for extremely sparse and extremely dense graphs respectively. Is there any reference to find a non-trivial (asymptotic) bound? For example, can we bound it as $O(m^\alpha n^\beta)$ for some $\alpha < 2$ and $\beta < 3$?

Answer 1

It's $\Theta(m^2)$ for multigraphs (consider a graph with $m$ edges between the same pair of nodes and all other nodes isolated) and $\Theta(mn)$ for simple graphs (the sum of squared degrees equals the number of directed two-edge walks; each edge can be continued to form a two-edge walk in $O(n)$ ways; consider $K_{m/n,n}$).

Answer 2

You may also like to know that this "sum of squares of the degrees" is also called "First Zagreb Index". When you type it in Google you get results like this one :

http://www.springerlink.com/content/a5352252v5376u37/