某类本原不可幂定号有向图的基指数

赵 晶,高玉斌

(中北大学理学院,山西太原030051)

1 问题的提出

一个实数 a的符号sgn a根据a＞0,a＜0或 a=0,被定义为1,-1或0.将一个有向图D(允许含有环但不能有重弧)中的每一条弧赋予符号1或-1所得的图称为D的定号有向图.定号有向图中的一条途径W是由一系列的弧e1,e2,…,ek组成的,并且ei的终点与ei+1的起点相同 (i=1,Λ,κ-1).途径W中所含弧的条数称为途径W的长度,记为l(W)[1].途径W的符号定义为W中所有弧的符号的乘积(重复出现的弧的符号重复计),即

设 D为有向图,如果存在正整数 k,使得对于 D中的任意顶点νi和νj(可以相同)都有从νi到νj的长为k的途径,则称D为本原的,满足上述条件的最小的k被称为D的本原指数,记为exp(D)[3].设D是一个本原有向图,对于νi∈D,存在正整数 p,使得对任意t≥p,从顶点νi到D中的任一点都有长为t的途径,满足上述条件的最小正整数 p,叫做顶点νi的点指数,记为expD(νi)[4].设S是一个本原不可幂定号有向图,使得对任意正整数 t≥l,及 S中任意两个顶点νi和νj(可以相同),从νi到νj都有长为t的SSSD途径对,则称满足上述条件的最小正整数l是定号有向图S的基,记为l(S)[5].

定义1.1[6]定号有向图中的两条途径W1和W2,如果它们有相同的起点、终点、长度,但有不同的符号,则称为SSSD途径对.

定义1.2[7]如果定号有向图S不包含SSSD途径对,则称S为可幂的,否则称S为不可幂的.

2 预备知识

引理 2.1[8,9]设S是一个本原定号有向图,则 S不可幂当且仅当S中存在两个不同的圈C1,C2(其长分别为 p1和 p2)满足下面两个条件之一:

(Ⅰ)pi是奇数,pj是偶数,并且有sgn Cj=-1(其中 i,j=1,2并且 i≠j);

(Ⅱ)p1和 p2都是奇数,并且有sgn C1=-sgn C2.

为了方便,称满足 (Ⅰ)或 (Ⅱ)的圈对 C1和 C2为“异圈对”.容易看到闭圈对W1=p2C1和W2=p1C2有相同的长度 p1p2,但有不同的符号:

设 a1,…,ak都为正整数,定义Frobenius集S(a1,…,ak)={r1a1+…+rkak|r1,…,rk都是非负整数}.根据Schur引理,如果 g.c.d(a1,…,ak)=1,那么 S(a1,…,ak)包含足够大的非负整数.在这种情况下,定义Frobenius数φ(a1,…,ak)为对于所有整数m≥φ,使得m∈S(a1,…,ak)成立的最小整数φ.根据上面的定义,有φ(a1,…,ak)-1∉S(a1,…,ak).另外,如果 a,b是互素的非负整数,那么

设R={l1,…,lk}是本原有向图D中圈长的集合,且 g.c.d(l1,…,lk)=1.对于 D中的每个顶点x和顶点y,用 d(x,y)表示从 x到y的距离,dR(x,y)(关于集合 R,从 x到y的相对距离)为从 x到y至少接触长为li(对于每个 i=1,…,r)的一个圈的最短途径的长度.记 φR=φ(l1,…lk)为Frobenius数,则对于本原指数和点指数有以下式子成立:

引理 2.2[10]设S是一个本原不可幂定号有向图,W1与W2是从点u到ν的长度为r的SSSD途径对,d(S)表示S的直径,则有以下不等式成立:

本文主要对一类本原不可幂定号有向图S进行研究,其基础图D为以下图1所示.显然,D包含3个圈,其中两个圈长相等为n-3,另一个圈长为n-1.通过研究得出如下主要结果.

3 主要结论

定理 3.1 设 S是一个n(n≥7)阶本原不可幂定号有向图,其基础图为 D(如图1所示).则

(Ⅰ)若S中的两个 n-3圈异号,则 l(S)=n2-4n+5.

(Ⅱ)若S中的两个n-3圈同号,则l(S)=2n2-9n+11.

证明 (Ⅰ)若 S中的两个n-3圈异号,令 Q1=(νn-2,ν2)+(ν2,ν3),Q2=(νn-2,νn)+(νn,ν3) 分别是从νn-2到ν3的长度为2的两条途径.另外,R={n-3,n-1},分别用 Cn-1,Cn-3表示 n -1圈与 n -3的圈.由并结合 ( 2 ),(3) 得expD(ν3)≤φ(n-1,n-3)+n-3=n2-5n+5. 根据 (4) 得 l (S)≤d(S)+r+exps(ν)≤n-2+2+n2-5n+5=n2-4n+5.接下来用反证法证明l(S)≥n2-4n+5,即证明从ν1到νn-1不存在长为 n2-4n+4的SSSD途径对.假设Wi(i=1,2)是任意两条从ν1到νn-1的长为 k =n2-4n+4的途径,显然,n2-4n+4≥1,即每个Wi至少要绕Cn-1一圈,且由若干个 Cn-1圈和 Cn-3圈组成.所以,存在非负整数 ai,bi,使得

图1 定号有向图 S的基础图D

与 φ(n-1,n-3)定义矛盾.

因此,a1=a2,b1=b2,即sgn W1=sgn W2.由此证得从ν1到νn-1不存在长为 k的SSSD途径对.

综上得出l(S)=n2-4n+5.

(Ⅱ)若S中的两个n-3圈同号,即 sgn Q1=sgn Q2.令 Q是从ν3到νn-2的长为 n-5的唯一途径.再令 P1=(νn-2,νn-1)+(νn-1,ν1)+(ν1,ν2)+(ν2,ν3),P2=(νn-2,ν2)+(ν2,ν3) 分别是从νn-2到ν3的长为4与2的途径.

由于S是本原不可幂的定号有向图,且S中仅有的3个圈是由两个圈n-3和一个n-1圈组成,根据引理2.1知,每个n-3圈与n-1圈都可以构成一个“异圈对”.则由 (1)易知 (n-1)Cn-3与 (n-3)Cn-1符号相反.因此,令W1=P1+(n-4)Cn-1,W2=P2+(n-2)Cn-3分别是从νn-2到ν3的长为 n2-5n+8的途径对.从而W1+Q=(n-3)Cn-1,W2+Q=(n-1)Cn-3,即有W1与W2符号相反.由此得出,W1与W2是一对从νn-2到ν3的长为 n2-5n+8的 SSSD途径对.接下来的证明类似 (Ⅰ)中证明,由(4)得l(S)≤d(S)+r+exps(ν)≤n-2+n2-5n+8+n2-5n+5=2n2-9n+11.接下来用反证法证明l(S)≥2n2-9n+11.即证明从ν1到ν2不存在长为 k=2n2-9n+10的 SSSD途径对.假设Wi(i=1,2)是任意两条从ν1到ν2的长为 k=2n2-9n+10的 SSSD途径对,容易看出2n2-9n+10≥1,则每个Wi都由若干个Cn-1圈和若干个 Cn-3圈组成,且至少要绕 Cn-1一圈.所以,存在非负整数 ai,bi,使得 k=l(Wi)=1+ai(n-1)+bi(n-3)(ai≥1,bi≥0),故有 (a2-a1)(n-1)=(b1-b2)(n-3).设 a2-a1=(n-3)x,下证 x=0.用反证法,如果 x≥1,则a2≥n-2(由a1≥1),所以有φ(n-1,n-3)-1=n2-6n+7=k-(n-1)(n-2)-1=(a2-n+2)(n-1)+b2(n-3)∈S(n-1,n-3)这与φ(n-1,n-3)的定义矛盾.故 a1=a2,b1=b2,即sgn W1=sgn W2.所以从ν1到ν2不存在长为 k的SSSD途径对.

综上得出l(S)=2n2-9n+11.

[1] Gao YB,Huang YH,Shao YL.Bases of primitive non-powerful singed symmetric digraphs with loops[J].A rs Combin,2009,90：383-388

[2] Li Z,Hall F,Stuart L.Irreducible powerful ray pattern matrices[J].Linear Algebra Appl,2002,342：47-58

[3] Liu BB.The period and base of a reducible sign pattern matrix[J].Discr Math,2007,307：3031-3039

[4] Gao YB.Generalized exponents of primitive two-colo red digraphs[J].Linear Algebra App l,2009,430：1550-1565

[5] Lundgren JR,Maybee JS.Some properties of a class of recursively defined digraphs[J].Syst Sci,1991,16(1)：29-36

[6] Wang LQ,Yan C.Local bases of primitive non-powerful signed digraphs[J].Discr Math,2009,309：748-754

[7] Liu BL,You LH.Bounds on the base of primitive nearly reducible sign pattern matrices[J].Linear Algebra App l,2006,418：863-881

[8] Gao YB,Shao YL,Shen J.Boundson the local bases of primitive non-powerful nearly reducible sign patterns[J].Linear Multil Algebra,2009,57(2)：205-215

[9] Ma HP.Bounds on the local bases of primitive non-powerful,minimally strong signed digraphs[J].Linear Algebra App l,2009,430：718-731

[10] You LH,Shao JY,Shan HY.Boundson the bases of irreducible generalized sign pattern matrices[J].Linear Algebra App l,2007,427：285-300