单弧灯图的本原指数  

Primitive Exponents of One-Arc Light Digraphs

作　　者：张学锋[1] 王建中[1] 高玉斌[1] 

机构地区：[1]中北大学理学院,山西太原030051

出　　处：《中北大学学报（自然科学版）》2008年第5期385-394,共10页Journal of North University of China(Natural Science Edition)

基　　金：山西省自然科学基金资助项目(2007011017)

摘　　要：一个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.

关 键 词：k+1色有向图 本原指数 Znám问题 

分 类 号：O157.5[理学—数学]