S. N. Kyazhin, “On adaptation of digraph local primitiveness conditions and local exponent estimations”, Prikl. Diskr. Mat., 2016, no. 4(34), 81

Abstract: For vertices

$i$ and

$j$ in a digraph

$\Gamma$ , the last is called

$i\times j$ -primitive if for some

$\gamma\in\mathbb{N}$ and any integer

$t\ge\gamma$ , there is a path of length

$t$ from

$i$ to

$j$ in

$\Gamma$ . The least such

$\gamma$ is called

$i\times j$ -exponent of

$\Gamma$ and is noted as

$i\times j\text{-exp}\,\Gamma$ . Because of mathematical model generality, it is not always easy to use the universal criterion of digraph

$i\times j$ -primitiveness and the universal estimation of digraph

$i\times j$ -exponent obtained by S. N. Kyazhin and V. M. Fomichev. In the paper, some criteria of digraph

$i\times j$ -primitiveness and an estimations of digraph

$i\times j$ -exponent in two special cases are given.
For vertices

$i$ and

$j$ being achievable from each other, that is, belonging to a strongly connected component

$U$ , the graph

$\Gamma$ is

$i\times j$ -primitive if and only if

$U$ is primitive. If

$\Gamma$ is

$i\times j$ -primitive, then

$i\times j\text{-exp}\,\Gamma\le u(r-1)+G(\hat{C})+\rho(i,\tilde{U}(\hat{C}))+\theta(\tilde{U}(\hat{C}),j)-\sum\limits_{s=1}^r(l_s+(s-2)\lambda_s)+1$ , where

$u$ is the number of vertices in

$U$ ;

$\hat{C}$ is a primitive system of

$k$ directed cycles in

$U$ of lengths

$l_1,\ldots,l_k$ ;

$\tilde{U}(\hat{C})$ is the set of vertices of digraph

$U(\hat{C})=\bigcup\limits_{C\in\hat{C}}C$ which contains

$r$ connected components,

$r\le k$ ;

$\lambda_s$ is the sum of lengths of directed cycles in the

$s$ -th connected component in

$U(\hat{C})$ ,

$s=1,\ldots,r$ ;

$G(\hat{C})=g(l_1,\ldots,l_k)$ is Frobenius number;

$\rho(i,J)$ is the least distance between

$i$ and a subset

$J$ of vertices;

$\theta(J,j)$ is the least distance between

$J$ and

$j$ .
For

$i$ not being achievable from

$j$ , the graph

$\Gamma$ is

$i\times j$ -primitive if and only if for some

$d\in\mathbb{N}$ and subset

$P$ of the set of paths from

$i$ to

$j$ , the set

$\mathrm{spc}\,P$ is

$d$ -full, and for some

$a\in\mathbb{Z}$ ,

$\text{spc}\,W(i,j)\supseteq \mathrm{spc}\,P+\mathbb{Z}(a,d)$ , where

$\mathrm{spc}\,W(i,j)$ is the set of path lengths from

$i$ to

$j$ ;

$\mathrm{spc}\,P$ is the set of path lengths in

$P$ ;

$d$ -full set is the complete residue system modulo

$d$ ;

$\mathbb{Z}(a,d)=\{z\in \mathbb{Z}: z=a+kd, k\in \mathbb{N}\}$ ;

$\text{spc}\,P+\mathbb{Z}(a,d)=\{x+y:(x,y)\in \text{spc}\,P\times\mathbb{Z}(a,d)\}$ . If

$\Gamma$ is

$i\times j$ -primitive, then

$i\times j\text{-exp}\,\Gamma\le \xi_d(\text{spc}\,P)+a+d$ , where

$\xi_d(\text{spc}\,P)$ is the minimal number in

$\mathbb{N}$ such that, for all

$a\in\{\xi_d(\text{spc}\,P),\xi_d(\text{spc}\,P)+1,\ldots, \xi_d(\text{spc}\,P)+d-1\}$ , there is

$b\in\text{spc}\,P$ that

$b\le a$ and

$b$ is congruent to

$a$ modulo

$d$ .
By means of the result the derivation of

$i\times j$ -primitiveness conditions and

$i\times j$ -exponent estimations for various classes of digraphs is reduced to the estimation of appropriate numbers

$a$ and

$d$ . The results simplify local primitiveness recognition for concrete mixing digraphs of cryptographic transformations.