5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Is O(mn^2) less trivial than the two bounds you mentioned? :) $\endgroup$ – Tsuyoshi Ito May 4 '12 at 17:49
9
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ ...and it is lower bounded always by $\Theta(m^2/n)$. As easily implied either by symmetry, or Cauchy-Schwarz. $\endgroup$ – Sariel Har-Peled May 6 '12 at 1:50
7
$\begingroup$

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/

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks Nathan. Knowing this term is certainly very useful. $\endgroup$ – Rachit May 7 '12 at 20:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.