易叔勇, 尤利华
(华南师范大学数学科学学院,广东广州 510631)
称有向图D是本原的,如果存在正整数k使得对于D中任意2点vi和vj(允许i=j),在D中都有从点vi到点vj的长为k的有向途径.这样的最小正整数k称为D的本原指数,记为exp(D).有向图D是本原的,当且仅当D是强连通的,且其所有有向圈长的最大公约数为1.


设W1与W2是带号有向图S中的2条有向途径,如果W1与W2有相同的起点、相同的终点、相同的长度,并且有不同的符号,则称W1与W2是一个SSSD途径对.如果S中不包含SSSD途径对,则称带号有向图S是可幂的,否则称S是不可幂的.


令V(S)={1,2,…,n},则S的顶点经过适当地重新标号可以满足lS(1)≤lS(2)≤…≤lS(n).此时称lS(k)是S的第k个局部基.显然l(S)=lS(n).
本文涉及的其他的一些概念与记号可参阅文献[1]-[3].
文献[4]研究了n阶本原不可幂对称带号有向图S,证明了l(S)≤2n;文献[5]研究了n阶本原不可幂带号有向图的局部基的上界及极图;文献[6]研究了n阶带环的本原反对称带号有向图的局部基,证明了lS(k)≤n+k.在本文中,我们研究了n阶无环的本原反对称带号有向图S的局部基lS(k),得到了lS(k)≤max{n+l-1,n+k-1}(这里l为S中最小奇圈的长),给出了k≥l时lS(k)=n+k-1的一个极图,进而证明了n阶无环的本原反对称带号有向图S的基指数l(S)≤2n-1,给出了达到上界的极图.
关于本原不可幂带号有向图,文献[3]给出了一个重要的刻画.
定理1[3]设S是一个本原带号有向图,则S是不可幂的当且仅当S中有长度为p1,p2的圈C1,C2,满足以下两情形之一:
(A1)p1是奇数,p2是偶数,sgnC2=-1;
(A2)p1和p2都是奇数,并且sgnC1=-sgnC2.称满足条件(A1)或者(A2)的一对圈C1,C2为违规圈对[3].容易验证,如果C1,C2是长……