Given an undirected graph $G=(V,E)$ find $\sum_{v\in V}\frac{1}{d(v)}$ where $d(v)$ is the degree of a vertex?

52 Views Asked by At

Given an undirected graph $G=(V,E)$ find $\sum_{v\in V}\frac{1}{d(v)}$ where $d(v)$ is the degree of a vertex?

I know that $\sum_{v\in V} d(v) = 2|E|$ and thus $$\sum_{v\in V}\frac{1}{d(v)} \geq \frac{|V|^2}{2|E|}$$ but I am not able to come up with an upper bound or a good asymptotic expression for this problem. Any ideas will be much appreciated.