Snakes in Powers of Complete Graphs
H. L. Abbott, P. Dierker · SIAM Journal on Applied Mathematics · 1977
A snake in a graph G is a simple circuit $\mathcal{S}$ in G such that every edge of G that joins two vertices $\mathcal{S}$ of is an edge of $\mathcal{S}$. Denote by $S( G )$ the length of a longest snake in G. Some lower bounds for $S( {K_n^d } )$ are obtained, where $K_n^d $ denotes the product of d copies of the complete graph $K_n $ on n vertices.