On adaptation of digraph local primitiveness conditions and local exponent estimations | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2016. № 4(34). DOI: 10.17223/20710410/34/7

For vertices i and j in a digraph Г, the last is called i х j-primitive if for some 7 e N and any integer t ^ 7, there is a path of length t from i to j in Г. The least such 7 is called i х j-exponent of Г and is noted as i х j-expT. Because of mathematical model generality, it is not always easy to use the universal criterion of digraph i х j-primitiveness and the universal estimation of digraph i х j-exponent obtained by S. N. Kyazhin and V. M. Fomichev. In the paper, some criteria of digraph i x j-primitiveness and an estimations of digraph i x j-exponent in two special cases are given. For vertices i and j being achievable from each other, that is, belonging to a strongly connected component U, the graph Г is i x j-primitive if and only if U is primitive. If Г is i x j-primitive, then i x j-expT < u(r - 1) + G(C) + p(i, U7(C)) + 0(t/(C), j) - r - E (1_s + ( - 2)A_s) + 1, where u is the number of vertices in U; C is a primitive s=1 system of k directed cycles in U of lengths 1₁,... , ; U((C) is the set of vertices of digraph U(C) = (J C which contains r connected components, r ^ k; A_s is the sum с ес of lengths of directed cycles in the s-th connected component in U((C), s = 1,..., r; G(C) = g(1₁,..., Zfc) is Frobenius number; p(i, J) is the least distance between i and a subset J of vertices; 0(J, j) is the least distance between J and j. For i not being achievable from j, the graph Г is i x j-primitive if and only if for some d G N and subset P of the set of paths from i to j, the set spc P is d-full, and for some a G Z, spc W(i, j) 5 spc P + Z(a, d), where spc W(i, j) is the set of path lengths from i to j; spc P is the set of path lengths in P; d-full set is the complete residue system modulo d; Z(a, d) = {z G Z : z = a + kd, k G N}; spc P + Z(a, d) = {ж + y : (ж, y) G G spcP x Z(a, d)}. If Г is i x j-primitive, then i x j-expT ^ £_d(spcP) + a + d, where £_d(spcP) is the minimal number in N such that, for all a G {{_d(spcP),{_d(spcP) + 1, ..., £_d(spc P) + d - 1}, there is b G spc P that b ^ a and b is congruent to a modulo d. By means of the result the derivation of i x j-primitiveness conditions and i x j -exponent estimations for various classes of digraphs is reduced to the estimation of appropriate numbers a and d. The results simplify local primitiveness recognition for concrete mixing digraphs of cryptographic transformations.