Structure of local primitive digraphs

For vertices i and j in a digraph Г, this digraph is said to be i x j-primitive if there exists an integer y such that, for any t ^ y, there is a path in Г of length t from i to j; in this case, the least y is called i x j-exponent of Г. The properties of the i x j-primitive digraph Г structure, used for calculation of the digraph i x j-exponent, are investigated. It is shown that i x j-primitive digraph Г is strongly connected or the strongly connected components in it are connected to each other with the some simple paths in which all the vertices except, perhaps, initial and final ones are acyclic. The set of these components is divided into k + 1 levels according to the distance from vertex i, namely the 0-th level contains the strongly connected component with i, the k-th level contains the strongly connected component with j, the t-th level contains the strongly connected components which don't belong to the previous t - 1 levels and are connected with some components on (t - 1)-th level, t = 1,..., k - 1. Also, it is shown that, for the transformation of the state set of the cryptographic alternating step generator constructed on the base of linear feedback shift registers of lengths n, m and r, the i x j-primitive mixing digraph, for each i E {1,..., m} and j E {m + n, m + n + r}, consists of three strongly connected components divided into two levels.

Keywords

Authors

References