On adaptation of digraph local primitiveness conditions and local exponent estimations
Prikladnaâ diskretnaâ matematika, no. 4 (2016), pp. 81-98.

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: $i\times j$-primitiveness, $i\times j$-exponent, digraph, strongly connected component.
@article{PDM_2016_4_a6,
     author = {S. N. Kyazhin},
     title = {On adaptation of digraph local primitiveness conditions and local exponent estimations},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {81--98},
     publisher = {mathdoc},
     number = {4},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2016_4_a6/}
}
TY  - JOUR
AU  - S. N. Kyazhin
TI  - On adaptation of digraph local primitiveness conditions and local exponent estimations
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2016
SP  - 81
EP  - 98
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2016_4_a6/
LA  - ru
ID  - PDM_2016_4_a6
ER  - 
%0 Journal Article
%A S. N. Kyazhin
%T On adaptation of digraph local primitiveness conditions and local exponent estimations
%J Prikladnaâ diskretnaâ matematika
%D 2016
%P 81-98
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2016_4_a6/
%G ru
%F PDM_2016_4_a6
S. N. Kyazhin. On adaptation of digraph local primitiveness conditions and local exponent estimations. Prikladnaâ diskretnaâ matematika, no. 4 (2016), pp. 81-98. http://geodesic.mathdoc.fr/item/PDM_2016_4_a6/

[1] Fomichev V. M., Kyazhin S. N., “Local primitiveness of graphs and matrices”, Diskretn. Anal. Issled. Oper., 24:1 (2017) (in Russian)

[2] Kyazhin S. N., Fomichev V. M., “Local primitiveness of graphs and nonnegative matrices”, Prikladnaya Diskretnaya Matematika, 2014, no. 3(25), 68–80 (in Russian)

[3] Sachkov V. N., Tarakanov V. E., Combinatorics of Non-Negative Matrices, TVP Publ., M., 2000 (in Russian) | MR

[4] Fomichev V. M., “The new universal estimation for exponents of graphs”, Prikladnaya Diskretnaya Matematika, 2016, no. 3(33), 78–84 (in Russian)