{"id":"arxiv/2607.25016","url":"https://arxiv.org/abs/2607.25016","tags":["math.CO","math.PR"],"score":0,"title":"On efficient graph covers and steered random walks","domain":"math.CO","source":"arxiv","authors":["Nathan Tung","Richard Ueltzen"],"reviews":0,"subject":"math.CO","summary":"We prove that the vertices of any $n$-vertex graph can be partitioned into pieces of radius $r = O(\\log n)$ such that the sum of the sizes of their closed neighborhoods is at most $4n$. This answers a recent question of Bukh and Dubroff and directly yields an improvement to their upper bound on the optimal cover time of the $ε$-steered random walk. We also demonstrate that our bound on $r$ is best possible up to a constant factor for graphs with strong vertex expansion.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-27","reactions":{}}