Detour Saturated Oriented Graphs

摘要

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) <= 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 Turan number t (n, k), while the minimum size is O (n).