Applied Graph Theory
Structural properties of minimal primitive digraphs
P. V. Lebedev Ltd "ASP Labs", Moscow, Russia
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.
UDC:
519.1
DOI:
10.17223/20710410/41/7