<p>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}$).</p>

CC BY-SA 3.0
2012-05-06T01:50:54.167Z
...and it is lower bounded always by $\Theta(m^2/n)$. As easily implied either by symmetry, or Cauchy-Schwarz.
Sariel Har-Peled
CC BY-SA 3.0
2012-05-04T17:50:40.053Z
2012-05-04T17:50:40.053Z
David Eppstein
<p>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 :</p>

<p><a href="http://www.springerlink.com/content/a5352252v5376u37/">http://www.springerlink.com/content/a5352252v5376u37/</a></p>

CC BY-SA 3.0
2012-05-07T20:50:19.823Z
Thanks Nathan. Knowing this term is certainly very useful.
Rachit
CC BY-SA 3.0
2012-05-04T21:02:03.967Z
2012-05-04T21:02:03.967Z
Nathann Cohen
<p>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.</p>

<p>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$.</p>

<p>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 &lt; 2$ and $\beta &lt; 3$? </p>

CC BY-SA 3.0
2012-05-04T17:49:09.137Z
Is O(mn^2) less trivial than the two bounds you mentioned? :)
Tsuyoshi Ito
<graph-theory><co.combinatorics>
Bounds on sum of squares of node degrees in undirected graphs
Rachit
# Bounds on sum of squares of node degrees in undirected graphs

(Asked by: username_0 on 2012-05-04)

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$?

**Tags:** graph-theory, co.combinatorics

> **Comments:**
> **username_1**: Is O(mn^2) less trivial than the two bounds you mentioned? :)  

---

## 2 answers

### Answer by username_2 on 2012-05-04. Score: 9

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}$).

> **Comments:**
> **username_3**: ...and it is lower bounded always by $\Theta(m^2/n)$. As easily implied either by symmetry, or Cauchy-Schwarz.  

---

### Answer by username_4 on 2012-05-04. Score: 7

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/>

> **Comments:**
> **username_0**: Thanks Nathan. Knowing this term is certainly very useful.  

---

