On improved universal estimation of exponents of digraphs | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2019. № 43. DOI: 10.17223/20710410/43/8

An improved formula for universal estimation of exponent is obtained for n-vertex primitive digraphs. A previous formula by A. L. Dulmage and N. S. Mendelsohn (1964) is based on a system C of directed circuits C₁,..., C_m, which are held in a graph and have lengths l1,...,lmwith gcd(l1,...,lm) = 1. A new formula is based on a similar circuit system C7, where gcd(l₁,..., l_m) = d ≥ 1. Also, the new formula uses r^s/d(C7), that is the length of the shortest path from i to j going through the circuit system C and having the length which is comparable to s modulo d, s = 0, . . . , d - 1. It is ¹Работа поддержана грантом РФФИ № 16-01-00226. 116 В. М. Фомичев shown, that expΓ ≤ 1 + F'(L(C)) + R(C), where ^(L) = d ∙ F(l₁∕d,... ,l_m/d) and F (a₁,..., a_m) is the Frobenius number, R((J) = maxmax{rS^/d(C7)}. For some class of _(i,j) s ^i,j 2k-vertex primitive digraphs, it is proved, that the improved formula gives the value of estimation 2k, and the previous formula gives the value of estimation 3k - 2.