On properties of primitive sets of digraphs with common cycles

Let $\hat{\Gamma}=\{\Gamma_1,\ldots,\Gamma_p\}$ be a set of digraphs with vertex set $V$, $p>1$, and $U^{(p)}$ be the union of digraphs $\Gamma_1\cup\ldots\cup\Gamma_p$ with no multiple arcs. The smallest number such that the union of $\mu$ digraphs of the set $\hat{\Gamma}$ contains all arcs of $U^{(p)}$ is denoted by $\mu$. Suppose $\hat{C}=\{C_1,\ldots,C_m\}$ is a set of elementary cycles. This set is called common for $\hat{\Gamma}$ if every digraph of the set $\hat{\Gamma}$ contains all cycles of the set $\hat{C}$. Assume that $C_1^*\cup\ldots\cup C_m^*=V$ where $C_i^*$ denotes the vertex set of $C_i$, $i=1,\ldots,m$. For a given digraph $\Gamma$, the loop-character index in the semigroup $\langle \Gamma \rangle$ is the smallest integer $h$ for which there is a loop on every vertex of $\Gamma^h$. In this paper, we study conditions for the set of digraphs with common cycles to be primitive. For $m\geq 1$, the set $\hat{\Gamma}$ with common cycles set $\hat{C}$ is primitive if and only if the digraph $U^{(p)}$ is primitive. If $\hat{\Gamma}$ is primitive, then $\text{exp}\,\hat{\Gamma} \leq \bigl((\mu-1)h+1\bigr)\text{exp}\,U^{(p)}$, where $h$ is the loop-character index in the semigroup $\langle \Gamma(\hat{C})\rangle$, $\Gamma(\hat{C})=C_1\cup\ldots\cup C_m$. For $m=1$, we establish an improved bound on the exponent. Let all digraphs of the primitive set $\hat{\Gamma}$ have a common Hamiltonian cycle, then $\text{exp}\,\hat{\Gamma} \leq(2n-1)\mu+\sum\limits_{\tau=1}^\mu{\bigl(F(l_1^\tau,\ldots,l_{m(\tau)}^\tau)+d_\tau-l_1^\tau\bigr)}$, where $l_1^\tau,\ldots,l_{m(\tau)}^\tau$ are all cycle lengths in $\Gamma_\tau$, ordered so that $l_1^\tau<\ldots<l_{m(\tau)}^\tau=n$, $d_\tau=\text{gcd}(l_1^\tau,\ldots,l_{m(\tau)}^\tau)$, $F(l_1^\tau,\ldots,l_{m(\tau)}^\tau)=d_\tau\Phi(l_1^\tau/ d_\tau,\ldots,l_{m(\tau)}^\tau/ d_\tau)$, $\Phi(l_1^\tau/ d_\tau,\ldots,l_{m(\tau)}^\tau/d_\tau)$ denotes the Frobenius number, $\tau=1,\ldots,\mu$. Finally, if $n=q^{\alpha}$, $q$ is prime, $\alpha\in \mathbb{N}$, $m=n^2$, then the number of primitive sets of $n$-vertex digraphs with a common Hamiltonian cycle equals $2^\sigma-2^\varepsilon$, where $\sigma=2^{m-n}$, $\varepsilon=2^{m/q-n}$.