This article is cited in
1 paper
Applied Theory of Coding, Automata and Graphs
The criterion of primitivity and exponent bounds for a set of digraphs with common cycles
Y. E. Avezova National Engineering Physics Institute "MEPhI", Moscow
Abstract:
In the present paper, we determine criteria of primitivity and bounds on the exponents for sets of digraphs with common cycles. Let
$\hat\Gamma=\{\Gamma_1,\dots,\Gamma_p\}$ be a set of digraphs with vertex set
$V$ and
$U^{(p)}$ be a union of digraphs
$\Gamma_1\cup\dots\cup\Gamma_p$ with no multiple arcs,
$p>1$. Suppose
$\hat C=\{C_1,\dots,C_m\}$ is a set of elementary cycles. This set is called common for
$\hat\Gamma$ if every digraph of the set
$\hat\Gamma$ contains all the cycles of the set
$\hat C$. In the paper, we consider the case when
$C_1^*\cup\dots\cup C_m^*=V$ where
$C_i^*$ denotes the vertex set of the cycle
$C_i$,
$i=1,\dots,m$. For a given digraph
$\Gamma$, the loop-character index of the semigroup
$\langle\Gamma\rangle$ is the smallest integer
$h$ such that there is a loop on every vertex of
$\Gamma^h$. For
$m>1$, the set
$\hat\Gamma$ with common cycles set
$\hat C$ is primitive if and only if the digraph
$U^{(p)}$ is primitive; and if
$U^{(p)}$ is primitive, then $\exp\hat\Gamma\leq(2n-1)p+\sum_{\tau=1}^p(F(L_\tau)+d_\tau-l_1^\tau)$ where
$L_\tau=\{l_1^\tau,\dots,l_{m(\tau)}^\tau\}$ is the set of all the cycle lengths in
$\Gamma_\tau$, ordered so that
$l_1^\tau<\dots<l_{m(\tau)}^\tau=n$,
$d_\tau=\mathrm{gcd}(L_\tau)$, $L_\tau/d_\tau=\{l_1^\tau/d_\tau,\dots,l_{m(\tau)}^\tau/d_\tau\}$,
$F(L_\tau)=d_\tau\Phi(L_\tau/d_\tau)$,
$\Phi(L_\tau/d_\tau)$ denotes the Frobenius number,
$\tau=1,\dots,p$.
Keywords:
Hamiltonian cycle, loop-character index, primitivity of digraphs set, exponent of digraph, exponent of digraphs set.
UDC:
519.1
DOI:
10.17223/2226308X/11/31