# Bounding $\Sigma_{v\in V}(d(v)(\Sigma_{v'}d(v'))$ in a graph

Let $G=(V,E)$ be graph, I know that $\Sigma_{v\in V}d(v)=O(|V|+|E|)$.

In my algorithm I go over each $v$ and for each $v$ I look at all of his neighbors and their neighbors and I do constant time work on each of them.

There are $d(v)$ neighbors for $v$, and if $v'$ is a neighbor of $v$ then he have $d(v')$ neighbors. This gives the sum $\Sigma_{v\in V}(d(v)(\Sigma_{v'}d(v'))$ where $v'$ in the index of the second sum goes over all the neighbors of $v$.

What is the time complexity of my algorithm ? what is a tight bound for the above sum ?

What is the time complexity of my algorithm when the graph is directed ? now we have $d_{out}$ wherever we had $d$ in the above sum

-
These are both going to be $O(n^{3})$. Assuming this is related to your cstheory question? – mjqxxxx Oct 21 '12 at 20:47
@mjqxxxx - what question ? cstheory.stackexchange.com/users/7956/belgi – Belgi Oct 21 '12 at 20:49

I think that you need some more information on the graph. For a general graph with $n$ vertices, the above sum is maximized for a complete graph. As for a complete graph: $$\Sigma_{v\in V}(d(v)(\Sigma_{v'}d(v')) = n(n-1)(n-1) = O(n^3) = O(|V|^3) = O(|E|^{1.5})$$