Hamiltonian-path distance congruence conjecture for Cartesian products of directed cycles

At least 24 years old · documented by

Let XX be the Cartesian product of kk directed cycles of lengths m1,m2,…,mkm_1,m_2,\ldots,m_k, where k≥3k\geq 3 and each mi≥2m_i\geq 2. For vertices uu and vv of XX, let dX(u,v)d_X(u,v) denote the length of a shortest directed path from uu to vv. Hamiltonian-path distance congruence conjecture. There is a Hamiltonian path from uu to vv if and only if

dX(u,v)≡−1(modgcd⁡(m1,m2,…,mk)).d_X(u,v)\equiv -1\pmod{\gcd(m_1,m_2,\ldots,m_k)}.

This generalizes the coprime-length case, in which the congruence condition is automatic, and remains open according to the supplied source.

References

Primary source

David Austin, Heather Gavlas and Dave Witte, “Hamiltonian Paths in Cartesian Powers of Directed Cycles”, arXiv:math/0110073 (2001).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.