Structure of local primitive digraphs

S. N. Kyazhin

Prikladnaya Diskretnaya Matematika. Supplement, no. 10 (2017), pp. 87-89.

Résumé

For vertices $i$ and $j$ in a digraph $\Gamma$, this digraph is said to be $i\times j$-primitive if there exists an integer $\gamma$ such that, for any $t\geq\gamma$, there is a path in $\Gamma$ of length $t$ from $i$ to $j$; in this case, the least $\gamma$ is called $i\times j$-exponent of $\Gamma$. The properties of the $i\times j$-primitive digraph $\Gamma$ structure, used for calculation of the digraph $i\times j$-exponent, are investigated. It is shown that $i\times j$-primitive digraph $\Gamma$ 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,\dots,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\times j$-primitive mixing digraph, for each $i\in\{1,\dots,m\}$ and $j\in\{m+n,m+n+r\}$, consists of three strongly connected components divided into two levels.

Détail

Keywords: local primitive digraph, strongly connected component, mixing graph, alternating step generator.

Bibliographie

[1] Kyazhin S. N., “O primenenii uslovii lokalnoi primitivnosti i otsenok lokalnykh eksponentov orgrafov”, Prikladnaya diskretnaya matematika, 2016, no. 4(34), 81–98 | MR

[2] Kyazhin S. N., Fomichev V. M., “Lokalnaya primitivnost grafov i neotritsatelnykh matrits”, Prikladnaya diskretnaya matematika, 2014, no. 3(25), 68–80

[3] Fomichev V. M., Metody diskretnoi matematiki v kriptologii, Dialog-MIFI, M., 2010, 424 pp.

[4] Kyazhin S. N., Fomichev V. M., “Peremeshivayuschie svoistva dvukhkaskadnykh generatorov”, Prikladnaya diskretnaya matematika. Prilozhenie, 2016, no. 9, 60–62