  RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  General information Latest issue Archive Impact factor Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Prikl. Diskr. Mat.: Year: Volume: Issue: Page: Find

 Personal entry: Login: Password: Save password Enter Forgotten password? Register

 Prikl. Diskr. Mat., 2017, Number 35, Pages 89–101 (Mi pdm570)  Applied Graph Theory

Conditions of primitivity and exponent bounds for sets of digraphs

Y. E. Avezovaa, V. M. Fomichevabc

a National Research Nuclear University MEPhI (Moscow Engineering Physics Institute), Moscow, Russia
b Financial University under the Government of the Russian Federation, Moscow, Russia
c The Institute of Informatics Problems of the Russian Academy of Sciences, Moscow, Russia

Abstract: For a set of digraphs $\hat\Gamma=\{\Gamma_1,…,\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…\cup\Gamma_p$ where each edge in $\Gamma_i$ is assigned the label $i$, $i=1,…,p$. Any walk of length $s$ in $\Gamma^{(p)}$ is assigned a word $w=w_1…w_s$ of length $s$ over the alphabet $\{1,…,p\}$, and the corresponding product of digraphs $\Gamma(w)=\Gamma_{w_1}\cdot…\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},…,w^{t_m}$, where $\mathrm{gcd}(t_1,…,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,…,C_m\}$ of lengths $l_1,…,l_m$ respectively, $m\geq1$, $l_1\leq…\leq l_m$, the digraph $\Gamma(w)$, $w=w_1…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…\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,…,\Gamma_{n-1}\}$ with vertex set $\{0,…,n-1\}$, where for some $l$, $n\geq l>1$, each $\Gamma_i$, $i\in\{0,…,n-1\}$, has a Hamiltonian cycle $(0,…,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,…,\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,…,\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.

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

DOI: https://doi.org/10.17223/20710410/35/8  Full text: PDF file (632 kB) References: PDF file   HTML file

UDC: 519.1

Citation: Y. E. Avezova, V. M. Fomichev, “Conditions of primitivity and exponent bounds for sets of digraphs”, Prikl. Diskr. Mat., 2017, no. 35, 89–101 Citation in format AMSBIB
\Bibitem{AveFom17} \by Y.~E.~Avezova, V.~M.~Fomichev \paper Conditions of primitivity and exponent bounds for sets of digraphs \jour Prikl. Diskr. Mat. \yr 2017 \issue 35 \pages 89--101 \mathnet{http://mi.mathnet.ru/pdm570} \crossref{https://doi.org/10.17223/20710410/35/8} 

• http://mi.mathnet.ru/eng/pdm570
• http://mi.mathnet.ru/eng/pdm/y2017/i1/p89

 SHARE:      Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles

This publication is cited in the following articles:
1. Ya. E. Avezova, “O primitivnosti nekotorykh mnozhestv peremeshivayuschikh orgrafov registrovykh preobrazovanii”, PDM. Prilozhenie, 2017, no. 10, 60–62  2. V. M. Fomichev, Ya. E. Avezova, A. M. Koreneva, S. N. Kyazhin, “Primitivity and local primitivity of digraphs and nonnegative matrices”, J. Appl. Industr. Math., 12:3 (2018), 453–469    3. Ya. E. Avezova, “Kriterii primitivnosti i otsenki eksponentov mnozhestva orgrafov s obschim mnozhestvom konturov”, PDM. Prilozhenie, 2018, no. 11, 102–104  4. Ya. E. Avezova, “Svoistva primitivnykh mnozhestv orientirovannykh grafov s obschim mnozhestvom konturov”, PDM, 2019, no. 43, 101–114  •  Contact us: math-net2020_02 [at] mi-ras ru Terms of Use Registration Logotypes © Steklov Mathematical Institute RAS, 2020