Conditions of primitivity and exponent bounds for sets of digraphs

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