一类(k+1)-色有向图的本原指数

本文定义了一类具有(k+1)-色(k+1)-圈的有向图D(A),得到了它本原的充要条件,并给出了它的本原指数.

单弧灯图的本原指数

一个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问题,应用组合矩阵论和图论的方法,给出了单弧灯图的本原指数的算法.