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₁,..., C_m} of directed circuits in the graph with lengths l₁,... ,l_m respectively such that gcd(/₁,..., l_m) = 1. A new formula is based on a similar circuit system C with gcd(l₁,..., l_m) = 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₁/d,... ,l_m/d) and F(a₁,..., a_m) 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.

Keywords

Authors

References