ON THE LENGTH OF SNAKES IN POWERS OF COMPLETE GRAPHS

Abstract

The conjecture stated in an earlier paper by the author that there is a constant $\lambda$ (independent from both $n$ and $k$) such that $S(K_{n}^{d})\ge \lambda n^{d-1}$ holds for every $n\ge 2$ and $d\ge 2$, where $S(K_{n}^{d})$ is the length of the longest snake (cycle without chords) in the Cartesian product $K_{n}^{d}$ of $d$ copies of the complete graph $K_{n}$, is proved.