Об улучшенной универсальной оценке экспонентов орграфов

Способ универсальной оценки экспонента $n$-вершинного примитивного орграфа, предложенный А. Далмэджем и Н. Мендельсоном (1964), сохранял до настоящего времени статус наилучшего среди всех известных универсальных оценок. Этот способ использует множество контуров $\hat{C}$ орграфа, длины которых равны $l_1,\ldots,l_m$, где НОД$(l_1,\ldots,l_m)=1$, и множество длин кратчайших путей $\{r_{i,j}(\hat{C}): 1\leq i,j\leq n\}$, проходящих из вершины $i$ в вершину $j$ через множество контуров $\hat{C}$. Улучшение этого способа использует множество контуров $\hat{C}$, где НОД$(l_1,\ldots,l_m)=d\geq 1$, и множество длин кратчайших путей $\{r_{i,j}^{s/d}(\hat{C}): s=0,\ldots,d-1; 1\leq i,j\leq n\}$ из вершины $i$ в вершину $j$, проходящих через множество контуров $\hat{C}$ и образующих полную систему вычетов по модулю $d$. Доказана оценка $\text{exp}\,\Gamma\leq 1+\hat{F}(L(\hat{C}))+R(\hat{C})$, где $\hat{F}(L)=d\cdot F(l_1/d,\ldots, l_m/d)$; $F(a_1,\ldots,a_m)$ — число Фробениуса; $R(\hat{C})=\max_{(i,j)}\max_s\{r_{i,j}^{s/d}(\hat{C})\}$. Построен класс орграфов с множеством вершин $\{0,\ldots,2k-1\}$, $k>2$, для которых новая оценка принимает значение $2k$ при чётных $k$ и $2k-1$ при нечётных $k$, в то время как оценка Далмэджа и Мендельсона принимает значение $3k-2$ при чётных $k$ и $3k-3$ при нечётных $k$.