单弧灯图的本原指数

Primitive Exponents of One-Arc Light Digraphs

一个k+1色有向图D是本原的,如果存在非负整数h0,h1,h2,…,hk,且h0+h1+h2+…+hk>0,使得D的每对顶点(i,j)都存在从i到j的(h0,h1,h2,…,hk)-途径,称h0+h1+h2+…+hk的最小值为D的本原指数.本文研究了一类k+1色有向图.结合数论中的Znám问题,应用组合矩阵论和图论的方法,给出了单弧灯图的本原指数的算法.

A （k ＋ 1 ）-colored digraph D is primitive if there exist nonnegative integers h0,h1,…,hk with h0＋h1＋…＋hk〉0, such that for each pair （i,j） of vertices there exists an （h0,h1,…,h,）-walk in D from i to j. The exponent of the primitive （kq-1）-colored digraph Dis the minimum value of h0＋h1＋…＋h, taken over all such h0,hl,…,hk. A class of （k＋1）-colored digraphs are discussed. Combining with the Znam problem in number theory, with the application of combinatorial matrix theory and graph theory, the algorithms about the primitive exponents of one-arc light digraphs are given.