Новая универсальная оценка экспонентов графов | Прикладная дискретная математика. 2016. № 3(33). DOI: 10.17223/20710410/33/6

Получена новая универсальная оценка экспонентов n-вершинных примитивных орграфов через характеристики содержащихся в орграфе контуров Ci,...,Ck длины l₁,..., lk соответственно, где (l₁,..., lk) = 1. Показано, что exp Г ^ n(r+1) + + g(l₁,...,l_k) + L, где r - число компонент связности орграфа C₁ u ... u C_k; g(l1,...,lk) -число Фробениуса; L - линейная комбинация длин определённых контуров орграфа Г. Дано уточнение оценки для некоторых частных случаев. Приведены примеры оценок экспонентов орграфов. Полученная универсальная оценка для многих n-вершинных примитивных орграфов улучшает известные оценки. Порядок её величины варьируется от O(n) до O(n). Оценка принимает наибольшие значения порядка O(n), только если кратчайший контур примитивной системы имеет длину порядка O(n). На графах Виландта полученная оценка совпадает с оценкой Виландта.