Свойства минимальных примитивных орграфов | Прикладная дискретная математика. 2015. № 2 (28).

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