Turán theorems and convexity invariants for directed graphs (Q941398): Difference between revisions

The paper is motivated by the desire to evaluate certain classical convexity invariants in the context of transitive closure of arcs in the complete digraph. It is shown that in a complete digraph on certain minimum number of vertices and arcs, it is possible to partition the arc set into two subsets whose transitive closures have an arc in common. More specifically, it is shown that a digraph has no transitive cycle if and only if it is a directed composition of directed cacti over a cover digraph. If the digraph is strong, then it has no transitive cycle if and only if the blocks of the digraph are precisely the directed cycles of the digraph. A digraph is unipathic if and only it is a directed composition of directed cacti over the cover digraph of a partial order in which all intervals are chains.