Arc-disjoint hamiltonian paths in Cartesian products of directed cycles

About 4 years old · traced to

Let C1,C2,…,CrC_1,C_2,\ldots,C_r be directed cycles of length at least 22, and let r≥2r\geq 2. Their Cartesian product is the digraph

C1□C2□⋯□Cr.C_1\mathbin{\Box}C_2\mathbin{\Box}\cdots\mathbin{\Box}C_r.

Arc-disjoint hamiltonian paths conjecture. The Cartesian product C1□C2□⋯□CrC_1\mathbin{\Box}C_2\mathbin{\Box}\cdots\mathbin{\Box}C_r has two arc-disjoint hamiltonian paths.

The claim is proved for r=2r=2 and for r≥4r\geq 4 in the paper, leaving the case of Cartesian products of three directed cycles as the only open case. Several broad families of three-cycle products are also known to satisfy the claim.

References

Primary source

Iren Darijani, Babak Miraftab and Dave Witte Morris, “Arc-disjoint hamiltonian paths in Cartesian products of directed cycles”, arXiv:2203.11017 (2022).

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.