Covering the Powers of the Complete Graph with a Bounded Number of Snakes

Abstract

Let $K_n^d$ be the product of $d$ copies of the complete graph $K_4$. Wojciechowski [4] proved that for any $d\ge 2$ the hypercube $K_2^d$ can be vertex covered with at most $16$ disjoint snakes. We show that for any odd integer $n\ge 3$, $d\ge 2$ the graph $K_n^d$ can be vertex covered with $2n^3$ snakes.