|
This article is cited in 2 scientific papers (total in 2 papers)
Applied Graph Theory
On adaptation of digraph local primitiveness conditions and local exponent estimations
S. N. Kyazhinab a National Research Nuclear University MEPhI (Moscow Engineering Physics Institute), Moscow, Russia
b Special Development Center of the Ministry of Defence of the Russian Federation, Moscow, Russia
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.
Keywords:
$i\times j$-primitiveness, $i\times j$-exponent, digraph, strongly connected component.
Citation:
S. N. Kyazhin, “On adaptation of digraph local primitiveness conditions and local exponent estimations”, Prikl. Diskr. Mat., 2016, no. 4(34), 81–98
Linking options:
https://www.mathnet.ru/eng/pdm562 https://www.mathnet.ru/eng/pdm/y2016/i4/p81
|
Statistics & downloads: |
Abstract page: | 223 | Full-text PDF : | 47 | References: | 47 |
|