The number of walks and degree powers in directed graphs

Fiol and Garriga proved that in undirected graphs the number $w_k$ of walks of length $k$ does not exceed the sum of the $k$-th powers of the vertex degrees, i.e., $w_k\leq\sum_{x\in V}d(x)^k$. Here, we propose a generalization of this inequality for directed graphs using the geometric mean of the sums of the $k$-th powers of in- and out-degrees, namely, $w_k^2\leq(\sum_{x\in V}\din(x)^k)(\sum_{y\in V}\dout(y)^k)$. Further, we show that this inequality can be generalized for the case of nonnegative matrices, i.e., the sum of entries of the $k$-th matrix power is bounded from above by the geometric mean of the sums of the $k$-th powers of the row sums and column sums.     «

Fiol and Garriga proved that in undirected graphs the number $w_k$ of walks of length $k$ does not exceed the sum of the $k$-th powers of the vertex degrees, i.e., $w_k\leq\sum_{x\in V}d(x)^k$. Here, we propose a generalization of this inequality for directed graphs using the geometric mean of the sums of the $k$-th powers of in- and out-degrees, namely, $w_k^2\leq(\sum_{x\in V}\din(x)^k)(\sum_{y\in V}\dout(y)^k)$. Further, we show that this inequality can be generalized for the case...     »