1
$\begingroup$

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.

$\endgroup$
0

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.