On properties of primitive sets of digraphs with common cycles

Y. E. Avezova

Prikladnaâ diskretnaâ matematika, no. 1 (2019), pp. 101-114.

Résumé

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}$.

Détail

Keywords: Hamiltonian digraph, primitive set of digraps, exponent of digraphs set.

Bibliographie

[1] Fomichev V. M., Methods of Discrete Mathematics in Cryptology, Dialog-MIFI Publ., M., 2010, 424 pp. (in Russian)

[2] Fomichev V. M., Mel'nikov D. A., Cryptographic Methods of Information Security, v. 1, Mathematical Aspects, YuRAYT Publ., M., 2016, 209 pp. (in Russian)

[3] Frobenius G., “Uber Matrizen aus nicht negativen Elementen”, Sitzungsber K. Preuss. Akad. Wiss., 1912, 456–477 | Zbl

[4] Dulmage A. L., Mendelsohn N. S., “The exponent of a primitive matrix”, Canad. Math. Bull., 1962, no. 5, 241–244 | DOI | MR | Zbl

[5] Harary F., Graph Theory, Addison-Wesley Publ., 1969, 275 pp. | MR | Zbl

[6] Perkins P., “A theorem on regular graphs”, Pacific J. Math., 2 (1912)

[7] Protasov Yu. V., “Semigroups of non-negative matrices”, Russian Math. Surveys, 65:6 (2010), 1186–1188 | DOI | DOI | MR | Zbl

[8] Cohen J. E., Sellers P. H., “Sets of nonnegative matrices with positive inhomogeneous products”, Linear Algebra Appl., 47 (1982), 185–192 | DOI | MR | Zbl

[9] Olesky D. D., Shader B., van den Driessche P., “Exponents of tuples of nonnegative matrices”, Linear Algebra Appl., 356:1–3 (2002), 123–134 | DOI | MR | Zbl

[10] Avezova Y. E., “O primitivnosti nekotorykh mnozhestv peremeshivayushchikh orgrafov registrovykh preobrazovaniy [On primitivity of some shift registers mixing digraphs sets].”, Prikladnaya Diskretnaya Matematika. Prilozheniye, 2017, no. 10, 60–62 (in Russian)

[11] Avezova Y. E., Fomichev V. M., “Conditions of primitivity and exponent bounds for sets of digraphs”, Prikladnaya Diskretnaya Matematika, 2017, no. 35, 89–101 (in Russian) | MR

[12] Avezova Y. E., “The criterion of primitivity and exponent bounds for a set of digraphs with common cycles”, Prikladnaya Diskretnaya Matematika. Prilozheniye, 2018, no. 11, 102–104 (in Russian)

[13] Kyazhin S. N., “Weight properties of primitive matrices”, Prikladnaya Diskretnaya Matematika. Prilozheniye, 2018, no. 11, 10–12 (in Russian)

[14] Protasov V. Yu., Voynov A. S., “Sets of nonnegative matrices without positive products”, Linear Algebra Appl., 437:3 (2012), 749–765 | DOI | MR | Zbl

[15] Voynov A. S., “Shortest positive products of nonnegative matrices”, Linear Algebra Appl., 439:6 (2013), 1627–1634 | DOI | MR | Zbl

[16] Blondel V. D., Jungers R. M., Olshevsky A., “On primitivity of sets of matrices”, Automatica, 61 (2015), 80–88 | DOI | MR | Zbl

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

[18] Avezova Y. E., Fomichev V. M., “Combinatorial properties of rectangular $0,1$-matrix systems”, Prikladnaya Diskretnaya Matematika, 2014, no. 2(24), 5–11 (in Russian)

[19] Fomichev V. M., “Properties of minimal primitive digraphs”, Prikladnaya Diskretnaya Matematika, 2015, no. 2(28), 86–96 (in Russian)

[20] Avezova Y. E., Fomichev V. M., “About one heritable character in cyclic semigroups of graphs”, Prikladnaya Diskretnaya Matematika. Prilozheniye, 2016, no. 9, 105–109 (in Russian)