Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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