On primitivity of some sets of shift registers mixing digraphs

In this paper, we determine some conditions of primitivity and bounds of exponents exp Г for some sets of digraphs Г = {Г₀,..., Г_п-1} with vertices 0,..., n - 1. We obtain the following results. Suppose that, for each i G {0,..., n - 1}, the digraph Г has the Hamiltonian cycle (0,..., n - 1) and the arc (i, (i + l) mod n), where n ^ l > 1. Then the set Г is primitive if and only if gcd(n, l - 1) = 1; in this case, n - 1 ^ exp Г ^ 2n - 2. Suppose each Г also has the arc (i, (i + A) mod n), n ^ A > l > 1, i G {0,..., n - 1}. Then the set Г is primitive if and only if gcd(n, l - 1, A - 1) = 1; in this case, exp Г ^ (V8n + 1 - 3)/2 and if gcd(n, l - 1) = 1, then the exponent is at most n - 1 + max{b, n - b +1}, where b = (A - 1)(l - 1)^^(n)-1 mod n and <^(n) denotes Euler's totient function. At last, suppose n is even and each Г has the cycle (0,..., n - 1) and the arc (i, (i + l) mod n) if i is even, the cycle (n - 1,..., 0) and the arc (i, (i + A) mod n) if i is odd. Then the set Г is primitive and its exponent is at most 2n - 2 if gcd(n, l - 1) = 1 or gcd(n, A + 1) = 1.

Keywords

Authors

References