An improved formula for the universal estimation of digraph exponents
An early formula by A. L. Dulmage and N. S. Mendelsohn (1964) for the universal estimation of n-vertex primitive digraph exponent is based on a system C = {C<sub>1</sub>,..., C<sub>m</sub>} of directed circuits in the graph with lengths l<sub>1</sub>,...,l<sub>m</sub> respectively such that gcd(/<sub>1</sub>,..., l<sub>m</sub>) = 1. A new formula is based on a similar circuit system C with gcd(l<sub>1</sub>,..., l<sub>m</sub>) = d ^ 1. Also, the new formula uses the values г^((7) that are the lengths of the shortest paths from a vertex i to a vertex j going through the circuit system C and having the length comparable to s modulo d, s E {0,...,d - 1}. It's shown, that expT ^ 1 + F(L(C')) + R(C) where F(L) = d · F(l<sub>1</sub>/d,...,l<sub>m</sub>/d) and F(a<sub>1</sub>,..., a<sub>m</sub>) is the Frobenius number, R((7) = max max{г^((7)}. For a class of 2k-vertex (i,j) <sup>s</sup> primitive digraphs, it is proved that the improved formula gives the value of estimation 2k, but the early formula gives the value of estimation 3k - 2.