Structural properties of minimal primitive digraphs

P. V. Lebedev

Prikladnaâ diskretnaâ matematika, no. 3 (2018), pp. 66-75.

Résumé

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)$.

Détail

Mots-clés : primitive matrix
Keywords: primitive digraph, strongly connected digraph.

Bibliographie

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

[2] Kogos K. G., Fomichev V. M., “Positive properties of non-negative matrices”, Prikladnaya Diskretnaya Matematika, 2012, no. 4(18), 5–13 (in Russian)

[3] Fomichev V. M., “Properties of minimal primitive digraphs”, Prikladnaya Diskretnaya Matematika, 2015, no. 2(28), 86–96 (in Russian) | DOI

[4] Harari F., Graph Theory, Addison-Wesley, 1969 | MR

[5] Bukhshtab A. A., Number Theory, Lan' Publ., SPb., 2008, 384 pp. (in Russian)