On constructing snakes in powers of complete graphs
The author proves a conjecture of H. L. Abbott and M. Katchalski that for every \(m\geq 2\) there is a positive constant \(\lambda_m\) such that \(S(K_{mn}^d)\geq \lambda_m n^{d-1} S(K_m^{d-1})\), where \(S(K_m^d)\) is the length of a longest chordless cycle (snake) in the Cartesian product \(K_m^d\) of \(d\) copies of the complete graph \(K_m\). As a corollary the author concludes that for any finite set \(P\) of primes there is a constant \(c= c(P)> 0\) such that \(S(K_n^d)\geq cn^{d-1}\) for any \(n\) divisible by an element of \(P\) and any \(d\geq 1\).
- A Method for Constructing Circuit Codes
- A new lower bound for snake-in-the-box codes
- Covering the hypercube with a bounded number of disjoint snakes
- Further results on snakes in powers of complete graphs
- scientific article; zbMATH DE number 36687 (Why is no real title available?)
- scientific article; zbMATH DE number 1792645 (Why is no real title available?)
- Long Snakes in Powers of the Complete Graph with an Odd Number of Vertices
- Maximal length of circuit in a unitary \(n\)-dimensional cube
- On the snake in the box problem
- Snakes and pseudo-snakes in powers of complete graphs
- Snakes in Powers of Complete Graphs
- The snake-in-the-box problem: A new upper bound
This page was built for publication: On constructing snakes in powers of complete graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1381860)
