Full-text PDF (642 kB)

DOI: https://doi.org/10.17223/20710410/41/7

Abstract: Let $\Gamma^P(n,m)$ be the set of all minimal primitive $n$-vertex digraphs with $m$ arcs. The purpose of the research is to describe the new classes of digraphs $\Gamma\in\Gamma^P(n,n+3)$ and their graph degree structures $D(\Gamma)$. This problem is important for the analysis of mixing properties of round transformations, e.g. symmetric iterative block ciphers. A matrix $M$ is said to be primitive if there is a power $M^e=\left(m_{i, j}^{(e)}\right)$ such that $m_{i, j}^{(e)}>0$ for all $i$ and $j$; the least power $e$ with this property is called an exponent of $M$. The conceptions of the primitiveness and exponent of the matrix $M$ expand to the digraph $\Gamma$ with the adjacency matrix $M$. The minimal primitive digraph is a digraph of which adjacency matrix loses its primitiveness property after replacing any positive element by zero. The main results of our research are the following: 1) for the minimal primitive digraph $\Gamma\in\Gamma^P(n,n+3)$, graph degree structures $D(\Gamma)$ are described via solutions of the equation $n_{1,2}+n_{2,1}+2n_{1,3}+2n_{2,2}+2n_{3,1}+3n_{1,4}+3n_{2,3}+3n_{3,2}+3n_{4,1}+\dots+(n-2)n_{n-1,1}= 6$ and represented in the table of $D(\Gamma)$ values; 2) it is proved that $D(\Gamma)$, for digraphs from the set $\Gamma^P(n,n+k)$, are determined and can be calculated by $D(\Gamma)$ for $\Gamma\in\Gamma^P(n-1,n+k-2)$; 3) it is proved that the number of classes of digraphs $\Gamma^P(n,n+k)$ could be estimated via solutions of the equation $n_{1,2}+n_{2,1}+2n_{1,3}+2n_{3,1}+3n_{1,4}+3n_{4,1}+4n_{1,5}+4n_{5,1}+\dots+kn_{1,k+1}+kn_{k+1,1}=2k$ and graph degree structures for $\Gamma\in\Gamma^P(n-1,n+k-2)$; 4) $N_3\leq34$ and $N_2\leq9$, where $N_i$ is the number of classes in $\Gamma^P(n,n+i)$.

Keywords: primitive matrix, primitive digraph, strongly connected digraph.

Bibliographic databases:

Citation: P. V. Lebedev, “Structural properties of minimal primitive digraphs”, Prikl. Diskr. Mat., 2018, no. 41, 66–75

Citation in format AMSBIB

Linking options:

https://www.mathnet.ru/eng/pdm635

https://www.mathnet.ru/eng/pdm/y2018/i3/p66

Citing articles in Google Scholar: Russian citations, English citations
Related articles in Google Scholar: Russian articles, English articles