Non-intersecting detours in strong oriented graphs

Abstract

One of the classical results in graph theory states that every two longest path in a connected graph (also called detours) have a vertex in common. The corresponding problem for three longest paths in a graph is still unsolved. For the oriented graphs one can easily construct a graph having k non-intersecting detours for any integer k ≥ 2. But the situation is more complicated if we require the oriented graph to be strong. We prove that for k ≤ 7 there is no strong oriented graph with non-intersecting detours of order k. For k ≥ 8 we provide a construction of an infinite class of strong oriented graphs with approximately √k non-intersecting detours.