2026/07/27 by Nathan Tung, Richard Ueltzen
Mathematics · #math.CO
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.