Blanket-cover time conjecture for graphs

About 14 years old · traced to

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.

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.