the.bay.news

Improved bounds for the variant of lazy cops and robbers on generalized hypercubes

arXiv.org
Improved bounds for the variant of lazy cops and robbers on generalized hypercubes
In the speed-$d$ variant of Lazy Cops and Robbers, the cops and the robber alternate turns. On a cop turn, either all cops remain stationary or one cop traverses a path of length at most $d$. On a robber turn, the robber either remains stationary or moves to an adjacent vertex. Let $c_{\mathrm L}^{(d)}(G)$ denote the minimum number of cops that can force a cop to occupy the robber's vertex after finitely many turns. We study this variant on the generalized hypercube $Q(n,m)$, whose vertex set is ${\{0,1,\ldots,m\}}^n$. For fixed integers $m\geq2$ and $d\geq1$, we prove that, as $n\to\infty$, \[ c_{\mathrm L}^{(d)}(Q(n,m)) =O\!\left(\frac{{(m+1)}^n}{n^{d+1/2}}\right). \] When $d=1$, our result improves the upper bound of Sim, Tan, and Wong for the ordinary lazy cop number by a factor of $\log n$.

0 comments

Sign in to join the discussion — your thebay.events account works here.

No comments yet.