Conditions of primitivity and exponent bounds for sets of digraphs | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2017. № 35. DOI: 10.17223/20710410/35/8

For a set of digraphs Г = {Г₁,..., Г_р}, p > 1, we present a criterion to be primitive. We do it in terms of characteristics of the multidigraph Г = Г₁U... U Г_р where each edge in Г is assigned the label i, i = 1,... ,p. Any walk of length s in Г is assigned a word w = w₁... w_s of length s over the alphabet {1,... ,p}, and the corresponding product of digraphs r(w) = r_wi · ... · r_Ws is introduced. The walk is assigned the label w if it is the concatenation of t walks labeled with w. The multidigraph Г is called w-strongly connected if it is strongly connected and, for all its vertices i and j, there exists a walk in Г from i to j labeled with w for some natural number t. By the definition, the set of digraphs Г is primitive if and only if r(w) is primitive for some word w. Thus, we have the following criterion: the digraph r(w) is primitive if and only if Г is w-strongly connected and has cycles labeled with w,..., w, where gcd(t₁,... ,t_m) = 1. As a corollary, we prove that the problem of recognizing the primitivity of Г is algorithmically decidable. In the particular case, when the digraphs in Г have the common set of cycles C = {C₁,...,C_m} of lengths l₁,...,l_m respectively, m ^ 1, l₁ ^ ... ^ l_m, the digraph r(w), w = w₁... w_s, is primitive if any one of the following conditions holds: a) m = 1 and l₁ = 1; b) gcd(l₁,..., l_m) = s; c) the digraph C₁ U ... U C_m is connected and has quasi-Eulerian C-cycle of length s. At last, for the set of digraphs Г = {r_o,...,Г_п-1} with vertex set {0,... , n - 1}, where for some l, n ^ l > 1, each Г^ i £ {0,... ,n - 1}, has a Hamiltonian cycle (0,..., n - 1) and the edge (i, (i + l) mod n), we prove the following criterion of primitivity and bounds for the exponent: the set Г = {Го,..., Г_п-1} is primitive if and only if gcd(n, l - 1) = 1, and in this case n - 1 ^ expT ^ 2n - 2. The minimal subset of Г = {Г^ ..., Г_п-1} with exponent 2n - 2 contains at most n/d digraphs, where d = gcd(n,l). The presented results are used for evaluating mixing properties of cryptographic functions compositions.