| |
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. One can easily construct an oriented graph having $q$ non-intersecting detours for any integer $q\ge 2$. But the situation is more complicated if we require the oriented graph to be strong. We prove that for $k\le 7$ there is no strong oriented graph with non-intersecting detours of order $k$. For $k\ge 8$ we provide a construction of an infinite class of strong oriented graphs with approximately $\sqrt{k}$ non-intersecting detours. Contact the authors: vaardsa@unisa.ac.za, semanisin@science.upjs.sk Download PDF version of the preprint. |