Arc-disjoint hamiltonian paths in Cartesian products of directed cycles

From papers

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

C1C2Cr.C_1\mathbin{\Box}C_2\mathbin{\Box}\cdots\mathbin{\Box}C_r.

Arc-disjoint hamiltonian paths conjecture. The Cartesian product C1C2CrC_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 r4r\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.

Progress summary

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

Sources & referencesView supporting material

Primary source

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

Solutions 0

No solutions have been posted yet.