Tight cover-time conjecture for minimum-degree weighting

From papers

Let GwG_w be a graph equipped with the minimum-degree weighting scheme, let nn be its number of vertices, and let dd be the parameter used in the locally tree-like analysis. Let COV[Gw]\text{{\bf COV}}[G_w] denote the resulting weighted random walk's cover time. Tight minimum-degree weighted cover-time conjecture. The bound in the source can be replaced by

COV[Gw](1+o(1))d1d2  nlogn.\text{{\bf COV}}[G_w] \leq (1+o(1))\frac{d-1}{d-2}\;n\log n.

This is presented as a sharper bound than the preceding weighted cover-time estimate. The source gives no resolution.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Mohammed Abdullah, “The Cover Time of Random Walks on Graphs”, arXiv:1202.5569 (2012).

Solutions 0

No solutions have been posted yet.