Primitive Exponents Of Two Classes Of Multicolor Digraphs

The primitivity of colored multidigraphs attracts much attention since it is related to properties of the Hurwitz produce of matrices. A multidigraph D with arcs colored by c₁, c₂,…, c_k is primitive if there exists a k-tupleα= (α₁,α₂,…,α_k) of nonegative integers such that for any u, v in V(D), there exists a (u, v)-walk which contains exactlyα_i arcs of color c_i for i = 1,2,…,k. If D is primitive, the exponent of D, denoted byexp(D), is the smallest value ofα₁+α₂+…+α_k over all suchα. The aim of this paperis to explore the primitivity and exponents of two classes of colored mutidigraphs.In Chapter 1, after a short introduction to the used basic notation and terminologyon graphs, we give some concepts and results on the primitivity of colored multidigraphs.In Section 2.1, we define a class of multidigraphs D₃^* with arcs colored by c₁,c₂ and show a necessary and sufficient condition for D₃^* to be primitive. In Section 2.2 and 2.3, we study the exponent of D₃^* which contains exactly two arcs colored by c₂. According to the locations of two arcs colored by c₂, the paper divides D₃^* into Type 1 and Type 2, and gives upper bounds of Type 1 and Type 2, respectively. The main results are as follows:(1) If D₃^* is Type 1, then the exponent of the two colored digraph exp(D₃^*)≤8n²-2n-1.(2) If D₃^* is Type 2, then the exponent of the two colored digraph exp(D₃^*)≤10n² -4n-3.In Section 3.1, we define a class of multidigraphs D^* which consists of k +1 cycles with length b₀ + ka₀, b₀ + a₁,…, b₀ + a_k, respectively, and is colored by c₁, c2,…, c_k+1, and show a necessary and sufficient condition for it to be primitive. In Section 3.2, we show the exponents of D^*. The main results are as follows:(1) If a₀/a₁+a₀/a₂+…+a₀/a_k+1/a₁a₂…a_k=1,then exp (D^*)=2(ka₀+1)a₁a₂…a_k-1;(2) If a₀/a₁+a₀/a₂+…+a₀/a_k+1/a₁a₂…a_k=1,then exp (D^*)=2(ka₀+1)a₁a₂…a_k-1;...