Path-pairable Cartesian products of two non-path-pairable graphs
Let and be graphs, and let denote their Cartesian product. A graph is path-pairable if every pairing of distinct vertices can be joined by pairwise edge-disjoint paths.
Cartesian-product conjecture. There exist non-path-pairable graphs and such that
is path-pairable.
The Cartesian product of two path-pairable graphs need not be path-pairable, so this conjecture asks whether path-pairability of either factor is necessary at all for path-pairability of the product. The source describes this as an open question and states that the proposed condition is believed not to be necessary.
References
- Gabor Meszaros, “On Path-Pairability of Cartesian Product of Complete Bipartite Graphs”, arXiv:1401.7929 (2015).
Progress summary
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.