van Aardt, Susan A.; Frick, Marietjie; Dunbar, Jean E.; Oellermann, Ortrud Detour saturated oriented graphs. (English) Zbl 1220.05053 Util. Math. 79, 167-180 (2009). Summary: The detour order of an oriented graph \(D\), denoted by \(\lambda(D)\), is the order of a longest path in \(D\). An oriented graph is said to be \(k\)-detour saturated if \(\lambda(D)\leq k\) and \(\lambda(D+ xy)> k\) for any two non-adjacent vertices \(x\) and \(y\) in \(D\). In this paper we characterize acyclic \(k\)-detour saturated oriented graphs. Since the strong component digraph of an oriented graph is acyclic, this characterization enables us to gain some insight into the structure of more complex oriented detour saturated graphs. We show that the maximum size of \(k\)-detour saturated oriented graphs of order \(n\) is the Turán number \(t(n,k)\), while the minimum size is \(O(n)\). Cited in 1 Document MSC: 05C20 Directed graphs (digraphs), tournaments 05C38 Paths and cycles 05C15 Coloring of graphs and hypergraphs Keywords:longest path; oriented graph; detour saturated; maximal nontraceable; digraph PDFBibTeX XMLCite \textit{S. A. van Aardt} et al., Util. Math. 79, 167--180 (2009; Zbl 1220.05053)