The criterion of primitivity and exponent bounds for a set of digraphs with common cycles

Y. E. Avezova

Prikladnaya Diskretnaya Matematika. Supplement, no. 11 (2018), pp. 102-104

Résumé

In the present paper, we determine criteria of primitivity and bounds on the exponents for sets of digraphs with common cycles. Let $\hat\Gamma=\{\Gamma_1,\dots,\Gamma_p\}$ be a set of digraphs with vertex set $V$ and $U^{(p)}$ be a union of digraphs $\Gamma_1\cup\dots\cup\Gamma_p$ with no multiple arcs, $p>1$. Suppose $\hat C=\{C_1,\dots,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 the cycles of the set $\hat C$. In the paper, we consider the case when $C_1^*\cup\dots\cup C_m^*=V$ where $C_i^*$ denotes the vertex set of the cycle $C_i$, $i=1,\dots,m$. For a given digraph $\Gamma$, the loop-character index of the semigroup $\langle\Gamma\rangle$ is the smallest integer $h$ such that there is a loop on every vertex of $\Gamma^h$. For $m>1$, the set $\hat\Gamma$ with common cycles set $\hat C$ is primitive if and only if the digraph $U^{(p)}$ is primitive; and if $U^{(p)}$ is primitive, then $\exp\hat\Gamma\leq(2n-1)p+\sum_{\tau=1}^p(F(L_\tau)+d_\tau-l_1^\tau)$ where $L_\tau=\{l_1^\tau,\dots,l_{m(\tau)}^\tau\}$ is the set of all the cycle lengths in $\Gamma_\tau$, ordered so that $l_1^\tau\dots$, $d_\tau=\mathrm{gcd}(L_\tau)$, $L_\tau/d_\tau=\{l_1^\tau/d_\tau,\dots,l_{m(\tau)}^\tau/d_\tau\}$, $F(L_\tau)=d_\tau\Phi(L_\tau/d_\tau)$, $\Phi(L_\tau/d_\tau)$ denotes the Frobenius number, $\tau=1,\dots,p$.

Détail

Keywords: Hamiltonian cycle, loop-character index, primitivity of digraphs set, exponent of digraph, exponent of digraphs set.

Bibliographie

[1] Fomichev V. M., Metody diskretnoi matematiki v kriptologii, Dialog-MIFI, M., 2010, 424 pp.

[2] Fomichev V. M., Melnikov D. A., Kriptograficheskie metody zaschity informatsii. Ch. 1. Matematicheskie aspekty, V 2 ch., Yurait, M., 2016, 209 pp.

[3] Avezova Ya. E., Fomichev V. M., “Usloviya primitivnosti i otsenki eksponentov mnozhestv orientirovannykh grafov”, Prikladnaya diskretnaya matematika, 2017, no. 35, 89–101 | MR

[4] Avezova Ya. E., “O primitivnosti nekotorykh mnozhestv peremeshivayuschikh orgrafov registrovykh preobrazovanii”, Prikladnaya diskretnaya matematika. Prilozhenie, 2017, no. 10, 60–62

[5] Avezova Ya. E., Fomichev V. M., “Ob odnom nasledstvennom priznake v tsiklicheskikh polugruppakh grafov”, Prikladnaya diskretnaya matematika. Prilozhenie, 2016, no. 9, 105–109