Blanket-cover time conjecture for graphs

Let G=(V,E)G=(V,E)) be a graph. For a random walk on GG, let COV[G]\text{{\bf COV}}[G] denote its cover time and let BCOV[G]\text{{\bf BCOV}}[G] denote the blanket-cover time, the expected first time at which every vertex vv has been visited at least πvCOV[G]\pi_v\text{{\bf COV}}[G] times, where πv\pi_v is the stationary probability of vv. Blanket-cover time conjecture.

BCOV[G]=O(COV[G]).\text{{\bf BCOV}}[G] = O(\text{{\bf COV}}[G]).

This conjecture asserts the equivalence, up to a constant factor, between blanket-cover time and cover time that was stated in the paper introducing blanket time. The source provides no resolution of the conjecture.

Sources & referencesView supporting material

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.