一类双色有向图的本原指数

Exponents of a Class of Two-Colored Digraphs

一个双色有向图D是本原的,当且仅当存在非负整数h,k,且h+k>0,使得D的每一对顶点(i,j)都存在从i到j的(h,k)-途径,称h+k的最小值为D的本原指数.文章研究了一类特殊的双色有向图,其未着色图含有n个2-圈和2个m-圈,对其着色进行了分类,研究了所给类的本原性,并给出了本原指数的上界.

A two-colored directed graph is primitive if and only if there exists nonnegative integers h and k with h＋k〉0 such that for each pair （i,j） of vertices there exists an （h,k）-walk in D from i to j. The exponent of D,denoted exp（D） ,is the smallest value of h＋k over all such h and k. In this paper, we consider the special two-colored digraphs whose uncoloed digraph consists of n 2-cycles and two m-cycles, we class its colored digraphs and figure out wether it is primitive, studying the tight upper bound on the exponents.