MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Hi All,

here is my question. I'm given a directed graph $(V,E)$ with $|V| = n$ vertices and in-degrees $d_1$, $d_2$ ... $d_n$ (so that $\sum_i d_i = |E|$). Can we upper bound the inverse (in)degree function $\sum_{i=1}^n \frac{1}{1+d_i}$ by something related to the independence number $\alpha$ of the (associated undirected version of the) graph ?
Assuming the graph is strongly connected is fine.

I know this is the case for undirected graphs, but I can't find any meaningful/sharp upper bounds for the directed case.

Thanks for your attention.

share|cite|improve this question
We solved the problem -- thanks. – user33888 May 10 '13 at 17:34

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.