Randomly n-cyclic digraphs (Q1065824)

A directed graph is called by the authors randomly n-cyclic if every directed path of length less than n can be extended to a directed cycle of length n. (The use of the adverb 'randomly' has no stochastic connotation; the conflict with the language of probabilistic combinatorics is unfortunate.) In this paper the authors show that every randomly n-cyclic directed graph has a spanning subgraph that is cyclically complete n-partite. A directed graph is cyclically complete n-partite if its vertex set is partitioned into nonempty sets \(V_ 0,...,V_{n-1}\) such that an edge joins vertex v to vertex w if and only if some i, \(v\in V_ i\) and \(w\in V_{i+1}\) (where \(V_ n\) is to be taken as \(V_ 0)\). Using this proposition they are able to characterize all randomly n-cyclic directed graphs for \(n=3,4\), and 5.