Odd-dimensional hypercube path-pairability conjecture

At least 11 years old · documented by

For k∈Nk\in\mathbb{N}, let Q2k+1Q_{2k+1} denote the (2k+1)(2k+1)-dimensional hypercube. A graph is path-pairable if every pairing of its vertices can be joined by pairwise edge-disjoint paths. Odd-dimensional hypercube conjecture. For every k∈Nk\in\mathbb{N},

Q2k+1Q_{2k+1}

is path-pairable. The source notes that even-dimensional hypercubes are not path-pairable, while Q1Q_1 and Q3Q_3 are path-pairable and the cases of odd dimension at least five were open.

References

Primary source

Ervin Györi, Tamás Róbert Mezei and Gábor Mészáros, “Note on Terminal-Pairability in Complete Grid Graphs”, arXiv:1606.06826 (2016).

Additional references

2 papers in this index state this conjecture (2014–2016). The statement above is taken from the most recent of them; the others are arXiv:1401.7929.

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.