Tight cover-time conjecture for minimum-degree weighting

About 14 years old · traced to

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))d−1d−2  nlog⁡n.\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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.