























We consider sparse digraphs generated by the configuration model with given in-degree and out-degree sequences. We establish that with high probability the cover time is linear up to a poly-logarithmic correction. For a large class of degree sequences we determine the exponent $γ\ge 1$ of the logarithm and show that the cover time grows as $n\log^γ(n)$, where $n$ is the number of vertices. The results are obtained by analysing the extremal values of the stationary distribution of the digraph. In particular, we show that the stationary distribution $π$ is uniform up to a poly-logarithmic factor, and that for a large class of degree sequences the minimal values of $π$ have the form $\frac1n\log ^{1-γ}(n)$, while the maximal values of $π$ behave as $\frac1n\log ^{1-κ}(n)$ for some other exponent $κ\in[0,1]$. In passing, we prove tight bounds on the diameter of the digraphs and show that the latter coincides with the typical distance between two vertices.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。