General information
Latest issue
Impact factor

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Prikl. Diskr. Mat.:

Personal entry:
Save password
Forgotten password?

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

This article is cited in 4 scientific papers (total in 4 papers)

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.


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
\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

Linking options:

    SHARE: FaceBook Twitter Livejournal

    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  mathnet  crossref
    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  mathnet  crossref  crossref  elib
    3. Ya. E. Avezova, “Kriterii primitivnosti i otsenki eksponentov mnozhestva orgrafov s obschim mnozhestvom konturov”, PDM. Prilozhenie, 2018, no. 11, 102–104  mathnet  crossref
    4. Ya. E. Avezova, “Svoistva primitivnykh mnozhestv orientirovannykh grafov s obschim mnozhestvom konturov”, PDM, 2019, no. 43, 101–114  mathnet  crossref
  • Прикладная дискретная математика
    Number of views:
    This page:154
    Full text:52

    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020