Conditions of primitivity and exponent bounds for sets of digraphs

Y. E. Avezova ; V. M. Fomichev

Prikladnaâ diskretnaâ matematika, no. 1 (2017), pp. 89-101.

Résumé

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.

Détail

Keywords: Wielandt's graph, primitive set of matrices (digraphs), exponent of digraph.

Bibliographie

[1] Sachkov V. N., Tarakanov V. E., Combinatorics of Non-Negative Matrices, TVP Publ., Moscow, 2000, 448 pp. (in Russian) | MR

[2] Knyazev A. V., Estimates for the Extreme Values of the Basic Metric Characteristics of Pseudosymmetric Graphs, Doctor of Physics and Mathematics Thesis, Moscow, 2002, 203 pp. (in Russian)

[3] Fomichev V. M., Methods of Discrete Mathematics in Cryptology, Dialog-MEPhI Publ., Moscow, 2010, 424 pp. (in Russian)

[4] Avezova Ya. E., Fomichev V. M., “Combinatorial properties of rectangular $0,1$-matrix systems”, Prikladnaya Diskretnaya Matematika, 2014, no. 2(24), 5–11 (in Russian)

[5] Fomichev V. M., Mel'nikov D. A., Cryptographic Methods of Information Security. Part 1. Mathematical Aspects, Yurayt Publ., Moscow, 2016, 209 pp. (in Russian)

[6] Kyazhin S. N., Fomichev V. M., “Local primitiveness of graphs and nonnegative matrices”, Prikladnaya Diskretnaya Matematika, 2014, no. 3(25), 68–80 (in Russian)

[7] Berzh K., Graph Theory and its Application, Foreign Literature Publ., Moscow, 1962, 320 pp. (in Russian) | MR

[8] Fomichev V. M., Kyazhin S. N., “Local primitiveness of matrices and graphs”, Diskretn. Anal. Issled. Oper., 24:1 (2017), 97–119 (in Russian) | DOI

[9] Fomichev V. M., “The new universal estimation for exponents of graphs”, Prikladnaya Diskretnaya Matematika, 2016, no. 3(33), 78–84 (in Russian)