Structural properties of minimal primitive digraphs | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2018. № 41. DOI: 10.17223/20710410/41/7

Let Г^р(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 Г £ Г^р(n, n + 3) and their graph degree structures D(r). 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 = (m^j such that (e) mjj > 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 Г 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 Г £ Г^р(n,n + 3), graph degree structures D(r) are described via solutions of the equation n₁ , ₂+n₂ д + 2n₁ , 3 + 2n₂ , ₂ + 2n₃ д + 3n₁ , ₄ + 3n₂ , 3 + + 3n₃ , ₂ + 3n₄ д + ... + (n - 2)n_n-1 д = 6 and represented in the table of D(r) values; 2) it is proved that D(r), for digraphs from the set Г^р(n, n + k), are determined and can be calculated by D(r) for Г £ Г^р (n - 1 , n + k - 2); 3) it is proved that the number of classes of digraphs Г^р(n, n + k) could be estimated via solutions of the equation n1 , 2 + n2 ,1 + 2щ , 3 + 2n3 д + 3n1 , 4 + 3n4 д + 4щ , 5 + 4n5 ,1 + ... + kn1 , k+1 + knfc₊1 д = 2k and graph degree structures for Г £ Г^р(n - 1,n + k - 2); 4) N₃ ^ 34 and N₂ ^ 9, where is the number of classes in Г^р(n, n + i).