The criterion of primitivity and exponent bounds for a set of digraphs with common cycles

In the present paper, we determine criteria of primitivity and bounds on the exponents for sets of digraphs with common cycles. Let Г = {Г₁,..., Г_р} be a set of digraphs with vertex set V and U⁽p) be a union of digraphs Г₁ U ... U Г_р with no multiple arcs, p > 1. 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 the cycles of the set C. In the paper, we consider the case when C* U ... U Cm = V where C* denotes the vertex set of the cycle C, i = 1,... ,m. For a given digraph Г, the loop-character index of the semigroup (Г) is the smallest integer h such that there is a loop on every vertex of For m > 1, the set Г with common cycles set C is primitive if and only if the digraph U⁽p) is primitive; and if U⁽p) is primitive, then exp Г ^ ((p - 1)h + 1) exp U⁽p) where h denotes the loop-character index of the semigroup (Г((7)), Г((7) = C₁ U ... U C_m. For m =1, some improvements are obtained. Let all the digraphs of the set Г contain a common Hamiltonian cycle. Then Г is primitive if and only if the greatest common divisor of all the distinct cycle lengths in U⁽p) is equal to 1; and if Г is primitive, then exp Г ^ (2n - 1)p + £ (f(L_t) + d_T - lJ j where L_T = {/J,..., l¹ m(_т)} is the set of all the cycle lengths in Г_т, ordered so that lJ < ... < l'^J m(_T) = n, d_T = gcd(L_T), L_Tjd_T = {/Jjd_T,... ,l¹ m(_T)jd_T}, F(L_T) = d_T&(L_Tjd_T), Ф^_тjd_T) denotes the Frobenius number, т = 1,... ,p.

Keywords

Authors

References