On properties of primitive sets of digraphs with common cycles | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2019. № 43. DOI: 10.17223/20710410/43/7

Let Γ = {Γ₁,..., Γ_p} be a set of digraphs with vertex set V, p > 1, and U^(p) be the union of digraphs Γ1 ∪ . . . ∪ Γp with no multiple arcs. The smallest number such that the union of μ digraphs of the set Γ contains all arcs of U^(p) is denoted by μ. Suppose C = {C₁,..., C_m} is a set of elementary cycles. This set is called common for Γ if every digraph of the set Γ contains all cycles of the set C. Assume that C1 ∪ ... ∪ Cm = V where C* denotes the vertex set of C_i, i = 1,..., m. For a given digraph Γ, the loopcharacter index in the semigroup (Γ) is the smallest integer h for which there is a loop on every vertex of Γ^h. In this paper, we study conditions for the set of digraphs with common cycles to be primitive. For m ≥ 1, the set Γ with common cycles set (J is primitive if and only if the digraph U^(p) is primitive. If Γ is primitive, then expΓ ≤ ≤ ((μ - 1)h + ^exp U^(p'', where h is the loop-character index in the semigroup (Γ(C7)), Γ(C7) = C₁ ∪ ... ∪ C_m. For m = 1, we establish an improved bound on the exponent. Let all digraphs of the primitive set Γ have a common Hamiltonian cycle, then expΓ ≤ ≤ (2n - 1)μ + (F (1T,..., im (_τ)) + dτ - 11), where 11,..., im (_τ) are all cycle lengths τ=1 in Γτ, ordered so that l₁^τ < ... < l^τ_m(τ) = n, dτ = gcd(l₁^τ,...,l_m^τ_(τ)), F(l₁^τ,...,l_m^τ_(τ)) = = d_τΦ(l1 /d_τ,..., im(_τ)∕d_τ), Φ(l₁ /d_τ,..., lm_τ)∕d_τ) denotes the Frobenius number, τ = = 1,..., μ. Finally, if n = q^a, q is prime, α ∈ N, m = n², then the number of primitive sets of n-vertex digraphs with a common Hamiltonian cycle equals 2^σ - 2^ε, where _{σ = 2}^m-n_{, ε = 2}^m/q-n_.