Properties of minimal primitive digraphs | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2015. № 2 (28).

It is proved that, for n ^ 4, the complexity of the determination of all n-vertex minimal primitive digraphs, which are parts of a given n-vertex primitive digraph Г, coincides with the complexity of the recognition of a monotone Boolean function in s variables where s is the number of arcs (i, j) in Г such that the vertex i out-degree and the vertex j in-degree exceed 1. It is found that, for n ^ 4, all the primitive n-vertex digraphs with n + 1 arcs are minimal graphs and there are minimal primitive n-vertex digraphs with the number of arcs from n + 2 to 2n - 3. Minimal primitive n-vertex digraphs with n + 1 and n + 2 arcs are described.