Свойства минимальных примитивных орграфов

При $n\ge4$ доказано, что сложность определения всех $n$-вершинных минимальных примитивных орграфов, являющихся частью заданного примитивного $n$-вершинного орграфа $\Gamma$, совпадает со сложностью распознавания монотонной булевой функции от $s$ переменных, где $s$ – число дуг $(i,j)$ в $\Gamma$, таких, что полустепень исхода вершины $i$ и полустепень захода вершины $j$ превышают 1. Установлено, что при $n\ge4$ все примитивные $n$-вершинные орграфы с числом дуг $n+1$ являются минимальными и имеются минимальные примитивные $n$-вершинные орграфы с числом дуг от $n+2$ до $2n-3$. Описаны минимальные примитивные $n$-вершинные орграфы с числом дуг $n+1$ и $n+2$.