Benutzer: Gast  Login
Autor(en):
Hanjo Täubig 
Titel:
The number of walks and degree powers in directed graphs 
Abstract:
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 th...    »
 
Stichworte:
directed graph, number of walks, in-degrees, out-degrees, nonnegative matrix, row sums, column sums, geometric mean 
Jahr:
2012 
Sprache:
en