Further results on snakes in powers of complete graphs (Q1182573)

Let \(S(G)\) denote the length of a longest chordless cycle (i.e., a snake) in a graph \(G\). The authors obtain a new lower bound for \(S(K^ d_ n)\), where \(K^ d_ n\) is the cartesian product of \(d\) copies of the complete graph \(K_ n\). In particular, they show that for \(n\equiv 0\pmod 4\) and \(d\geq 3\), \(S(K^ d_ n)\geq(n/2)^{d-1}S(K_ 2^{d- 1})\). Since it was shown in [Mat. Zametki 6, 309-329 (1969)] that there is a constant \(\lambda>0\) such that \(S(K_ 2^ d)>\lambda 2^ d\), it follows that for \(n\equiv 0\pmod 4\) and \(d\geq 3\), \(S(K^ d_ n)>\lambda n^{d-1}\).