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 = {C1,..., Cm} of directed circuits in the graph with lengths l1,...,lm respectively such that gcd(/1,..., lm) = 1. A new formula is based on a similar circuit system C with gcd(l1,..., lm) = 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(l1/d,...,lm/d) and F(a1,..., am) is the Frobenius number, R((7) = max max{г^((7)}. For a class of 2k-vertex (i,j) s 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.