Об улучшенной универсальной оценке экспонентов орграфов | Прикладная дискретная математика. 2019. № 43. DOI: 10.17223/20710410/43/8

Способ универсальной оценки экспонента n-вершинного примитивного орграфа, предложенный А. Далмэджем и Н. Мендельсоном (1964), сохранял до настоящего времени статус наилучшего среди всех известных универсальных оценок. Этот способ использует множество контуров (J орграфа, длины которых равны l₁,...,l_m, где НОД(1₁ ,..., l_m) = 1, и множество длин кратчайших путей {ri,j(c7) : 1 ≤ i,j ≤ n}, проходящих из вершины i в вершину j через множество контуров (J. Улучшение этого способа использует множество контуров (J, где НОД(1₁, ..., l_m) = d 1, и множество длин кратчайших путей {r^s∕j∙^d(C7) : s = = 0,..., d-1; 1 ≤ i,j ≤ n} из вершины i в вершину j, проходящих через множество контуров (J и образующих полную систему вычетов по модулю d. Доказана оценка expΓ ≤ 1 + I^(L(C)) + R(C), где F^{^}(L) = d• F(l₁∕d,..., l_m∕d); F(a₁,..., a_m) - число Фробениуса; R(C7) = maxmax{rSj^d(C7)}. Построен класс орграфов с множеством (i,j) s ^i,j вершин {0, . . . , 2k - 1}, k > 2, для которых новая оценка принимает значение 2k при чётных k и 2k - 1 при нечётных k, в то время как оценка Далмэджа и Мендельсона принимает значение 3k - 2 при чётных k и 3k - 3 при нечётных k.