On properties of primitive sets of digraphs with common cycles
Prikladnaâ diskretnaâ matematika, no. 1 (2019), pp. 101-114

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

Let $\hat{\Gamma}=\{\Gamma_1,\ldots,\Gamma_p\}$ be a set of digraphs with vertex set $V$, $p>1$, and $U^{(p)}$ be the union of digraphs $\Gamma_1\cup\ldots\cup\Gamma_p$ with no multiple arcs. The smallest number such that the union of $\mu$ digraphs of the set $\hat{\Gamma}$ contains all arcs of $U^{(p)}$ is denoted by $\mu$. Suppose $\hat{C}=\{C_1,\ldots,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 cycles of the set $\hat{C}$. Assume that $C_1^*\cup\ldots\cup C_m^*=V$ where $C_i^*$ denotes the vertex set of $C_i$, $i=1,\ldots,m$. For a given digraph $\Gamma$, the loop-character index in the semigroup $\langle \Gamma \rangle$ is the smallest integer $h$ for which there is a loop on every vertex of $\Gamma^h$. In this paper, we study conditions for the set of digraphs with common cycles to be primitive. For $m\geq 1$, the set $\hat{\Gamma}$ with common cycles set $\hat{C}$ is primitive if and only if the digraph $U^{(p)}$ is primitive. If $\hat{\Gamma}$ is primitive, then $\text{exp}\,\hat{\Gamma} \leq \bigl((\mu-1)h+1\bigr)\text{exp}\,U^{(p)}$, where $h$ is the loop-character index in the semigroup $\langle \Gamma(\hat{C})\rangle$, $\Gamma(\hat{C})=C_1\cup\ldots\cup C_m$. For $m=1$, we establish an improved bound on the exponent. Let all digraphs of the primitive set $\hat{\Gamma}$ have a common Hamiltonian cycle, then $\text{exp}\,\hat{\Gamma} \leq(2n-1)\mu+\sum\limits_{\tau=1}^\mu{\bigl(F(l_1^\tau,\ldots,l_{m(\tau)}^\tau)+d_\tau-l_1^\tau\bigr)}$, where $l_1^\tau,\ldots,l_{m(\tau)}^\tau$ are all cycle lengths in $\Gamma_\tau$, ordered so that $l_1^\tau\ldots$, $d_\tau=\text{gcd}(l_1^\tau,\ldots,l_{m(\tau)}^\tau)$, $F(l_1^\tau,\ldots,l_{m(\tau)}^\tau)=d_\tau\Phi(l_1^\tau/ d_\tau,\ldots,l_{m(\tau)}^\tau/ d_\tau)$, $\Phi(l_1^\tau/ d_\tau,\ldots,l_{m(\tau)}^\tau/d_\tau)$ denotes the Frobenius number, $\tau=1,\ldots,\mu$. Finally, if $n=q^{\alpha}$, $q$ is prime, $\alpha\in \mathbb{N}$, $m=n^2$, then the number of primitive sets of $n$-vertex digraphs with a common Hamiltonian cycle equals $2^\sigma-2^\varepsilon$, where $\sigma=2^{m-n}$, $\varepsilon=2^{m/q-n}$.
Keywords: Hamiltonian digraph, primitive set of digraps, exponent of digraphs set.
@article{PDM_2019_1_a6,
     author = {Y. E. Avezova},
     title = {On properties of primitive sets of digraphs with common cycles},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {101--114},
     publisher = {mathdoc},
     number = {1},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2019_1_a6/}
}
TY  - JOUR
AU  - Y. E. Avezova
TI  - On properties of primitive sets of digraphs with common cycles
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2019
SP  - 101
EP  - 114
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2019_1_a6/
LA  - ru
ID  - PDM_2019_1_a6
ER  - 
%0 Journal Article
%A Y. E. Avezova
%T On properties of primitive sets of digraphs with common cycles
%J Prikladnaâ diskretnaâ matematika
%D 2019
%P 101-114
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2019_1_a6/
%G ru
%F PDM_2019_1_a6
Y. E. Avezova. On properties of primitive sets of digraphs with common cycles. Prikladnaâ diskretnaâ matematika, no. 1 (2019), pp. 101-114. http://geodesic.mathdoc.fr/item/PDM_2019_1_a6/