易叔勇， 尤利華

(華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院，廣東廣州 510631)

稱有向圖D是本原的,如果存在正整數(shù)k使得對于D中任意2點vi和vj(允許i=j),在D中都有從點vi到點vj的長為k的有向途徑.這樣的最小正整數(shù)k稱為D的本原指數(shù),記為exp(D).有向圖D是本原的,當(dāng)且僅當(dāng)D是強(qiáng)連通的,且其所有有向圈長的最大公約數(shù)為1.

設(shè)W1與W2是帶號有向圖S中的2條有向途徑，如果W1與W2有相同的起點、相同的終點、相同的長度,并且有不同的符號,則稱W1與W2是一個SSSD途徑對.如果S中不包含SSSD途徑對,則稱帶號有向圖S是可冪的,否則稱S是不可冪的.

令V(S)={1,2,…,n},則S的頂點經(jīng)過適當(dāng)?shù)刂匦聵?biāo)號可以滿足lS(1)≤lS(2)≤…≤lS(n).此時稱lS(k)是S的第k個局部基.顯然l(S)=lS(n).

本文涉及的其他的一些概念與記號可參閱文獻(xiàn)[1]-[3].

文獻(xiàn)[4]研究了n階本原不可冪對稱帶號有向圖S,證明了l(S)≤2n;文獻(xiàn)[5]研究了n階本原不可冪帶號有向圖的局部基的上界及極圖;文獻(xiàn)[6]研究了n階帶環(huán)的本原反對稱帶號有向圖的局部基,證明了lS(k)≤n+k.在本文中，我們研究了n階無環(huán)的本原反對稱帶號有向圖S的局部基lS(k),得到了lS(k)≤max{n+l-1,n+k-1}(這里l為S中最小奇圈的長),給出了k≥l時lS(k)=n+k-1的一個極圖,進(jìn)而證明了n階無環(huán)的本原反對稱帶號有向圖S的基指數(shù)l(S)≤2n-1,給出了達(dá)到上界的極圖.

1 預(yù)備知識

關(guān)于本原不可冪帶號有向圖,文獻(xiàn)[3]給出了一個重要的刻畫.

定理1[3]設(shè)S是一個本原帶號有向圖,則S是不可冪的當(dāng)且僅當(dāng)S中有長度為p1,p2的圈C1,C2,滿足以下兩情形之一:

(A1)p1是奇數(shù),p2是偶數(shù),sgnC2=-1;

(A2)p1和p2都是奇數(shù),并且sgnC1=-sgnC2.稱滿足條件(A1)或者(A2)的一對圈C1,C2為違規(guī)圈對[3].容易驗證,如果C1,C2是長度分別是p1,p2的違規(guī)圈對,則閉途徑W1=p2C1(走長為p1的圈p2次)和W2=p1C2有相同的長度p1p2和不同的符號.

設(shè)S是一個本原反對稱的帶號有向圖,則由定理1易知S是不可冪的.

引理2[5]設(shè)S是一個n階本原不可冪帶號有向圖,則lS(k)≤lS(k-1)+1 (2≤k≤n).

2 主要結(jié)果與證明

設(shè)D為有向圖,W是D中一條途徑,記QW(x→y)為W上從x到y(tǒng)的最短路,l(W)表示途徑W的長度.

設(shè)n為奇數(shù),定義D1=(V,E),其中V={1,2,…,n},E={(i,i+1),(i+1,i),1≤i≤n-1}∪{(n,1),(1,n)},則易證D1是n階本原有向圖.

證明易證從點u到點u不存在長為n-2的途徑,所以expD1(u)≥n-1.

下證expD1(u)≤n-1.由D1的強(qiáng)連通性及對稱性可知,只需證明從點1到任何點i(1≤i≤n)都有長為n-1的途徑即可.

再證點1到任何點i(2≤i≤n)都有長為n-1的途徑.取

綜上，expD1(u)=n-1.

證明按l的取值分如下2種情形討論.

情形1:當(dāng)l=1時.此時點u是環(huán)點,故點u到任何一點都有長為n-1的途徑,進(jìn)而有長大于n-1的途徑,故有expS(u)≤n-1.

從而W是點u到點v的長為n-1的途徑.

綜合情形1和情形2可知expS(u)≤n-1,證畢.

定理2 設(shè)S是一個n階無環(huán)的本原反對稱帶號有向圖,l是S中最小奇圈的長,則對任意的k(1≤k≤n),有l(wèi)S(k)≤max{n+l-1,n+k-1}.

顯然,當(dāng)1≤k≤l時,lS(k)≤n+l-1.

當(dāng)k>l時,由引理2知

lS(k)≤lS(l)+(k-l)≤n+l-1+k-l=n+k-1.

故

結(jié)論得證.

由l(S)=lS(n)及定理2易知下面結(jié)論成立.

定理3 設(shè)S是n階無環(huán)的本原反對稱帶號有向圖,則l(S)≤2n-1.

下面將說明定理2和定理3中的上界是可達(dá)的.設(shè)d(u,v)表示在有向圖點u到點v的距離.為此，先證明下面的引理.

引理5 設(shè)S是本原不可冪帶號有向圖,W1和W2是點u到點u的長為r的SSSD途徑對,v是S中任意的一點,則lS(v)≤d(v,u)+r+expS(u).

設(shè)l(≥3)為奇數(shù),定義Dn,l=(V,E),其中V={v1,v2,…,vn},E={(vi,vi+1),(vi+1,vi),1≤i≤n-1,且i≠l}∪{(v1,vl),(vl,v1)}∪{(v1,vl+1),(vl+1,v1)}.顯見,Dn,l是n階無環(huán)的本原對稱帶號有向圖.

定理4 設(shè)l(≥3)為奇數(shù),n≥(3l-1)/2,S=Sn,l是以Dn,l為基礎(chǔ)有向圖的n階無環(huán)的本原反對稱帶號有向圖,則

由S是反對稱的可知，點v(l+1)/2到點v(l+1)/2有長為l的SSSD途徑對.下面分3種情形來討論.

情形1：當(dāng)1≤i≤(l+1)/2時.由引理5可知

lS(vi)≤d(vi,v(l+1)/2)+r+expS(v(l+1)/2)≤

下面證明從點vi到點vn不存在長為n+l-i-1的SSSD途徑對.

注意到點vi到點vn恰有2條路，即Q1=vivi-1…v2v1vl+1…vn,Q2=vivi+1…vlv1vl+1…vn,則l(Q1)=n-l+i-1,l(Q2)=n-i+1.設(shè)Wj(j=1,2)是點vi到點vn的長為n+l-i-1的SSSD途徑對,則Wj(j=1,2)由點vi到點vn的路Rj、若干個長為l的圈Cl和若干個長為2的圈C2之并,故可設(shè)l(Wj)=l(Rj)+ajl+2bj,aj≥0,bj≥0,j=1,2.

子情形1.1：若R1=R2=Q1.此時

n+l-i-1=n-l+i-1+ajl+2bj,aj≥0,bj≥0 (j=1,2)

得(2-aj)l=2(bj+i),從而0≤aj<2 (j=1,2).若aj=1,則得到奇數(shù)=偶數(shù)的矛盾；若aj=0,則a1=a2,b1=b2,進(jìn)而W1=W2,sgnW1=sgnW2.矛盾.

子情形1.2：若R1=R2=Q2.此時易得(1-aj)l=2(bj+1) (j=1,2),顯然aj<1,即aj=0，從而得到奇數(shù)=偶數(shù)的矛盾.

子情形1.3：若R1≠R2,不妨設(shè)R1=Q1,R2=Q2.類似子情形1.2得到矛盾.

綜上可得點vi到點vn不存在長為n+l-i-1的SSSD途徑對,故當(dāng)1≤i≤(l+1)/2時,lS(vi)=n+l-i.

情形2：當(dāng)(l+3)/2≤i≤l時.由對稱性易知lS(vi)=lS(vl+2-i)((l+3)/2≤i≤l),從而由情形1可立得lS(vi)的值.

情形3：當(dāng)l

lS(vi)≤d(vi,v(l+1)/2)+r+expS(v(l+1)/2)≤

類似情形1，可證從點vi到點vn不存在長為n+i-2的SSSD途徑對.故當(dāng)l

由上面的討論可知，點v(l+1)/2和點v(l+3)/2對應(yīng)最小的局部基指數(shù)lS(1),點v(l-1)/2和點v(l+5)/2對應(yīng)次小的局部基指數(shù)lS(2),依此類推,……,故可以直接寫出第k個局部基的表達(dá)式,即

顯然,定理4說明了當(dāng)k≥l時,定理2中的上界是可達(dá)的.又注意到當(dāng)取k=n時l(S)=2n-1,故圖Sn,l也是定理3中達(dá)到上界的一個極圖.

我們注意到文獻(xiàn)[6]研究了n階帶環(huán)的本原反對稱帶號有向圖的局部基,證明了lS(k)≤n+k,即

定理5[6]設(shè)S是n階帶環(huán)的本原反對稱帶號有向圖,則有l(wèi)S(k)≤n+k.

由l(S)=lS(n)及定理5易知有下面的結(jié)論成立.

推論1 設(shè)S是n階帶環(huán)的本原反對稱帶號有向圖,則有l(wèi)(S)≤2n.

易見,推論1中的上界也是可達(dá)的.取S2=(V,E),V={1,2,…,n},E={(i,i+1),(i+1,i),1≤i≤n-1}∪{(n,n)},且對任意的i(1≤i≤n-1),sgn(i,i+1)=+1,sgn(i+1,i)=-1,sgn(n,n)=+1.顯見,S2是n階帶環(huán)的本原反對稱帶號有向圖,由于點1到點1沒有長為2n-1的SSSD途徑對，所以l(S2)=2n.

由定理3和推論1,易得

推論2 設(shè)S是n階本原反對稱帶號有向圖,則有l(wèi)(S)≤2n.

容易看到,推論2中的最大值和次大值都是可達(dá)的.

參考文獻(xiàn)：

[1] BRUALDI R A,RYSER H J. Combinatorical matrix theory[M].Combridge: Combridge Univ Press, 1991: 53-87.

[2] BONDY J A,MURTY U S R. Graph theory with application[M]. London: Macmillan, 1976.

[3] YOU Lihua, SHAO Jiayu, SHAN Haiying. Bounds on the bases of irreducible generalized sign pattern matrices[J]. Linear Algebra Appl, 2007,427: 285-300.

[4] CHENG Bo, LOU Bolian.The bases sets of primitive zero-symmetric sign parrern matrices[J].Linear Algebra Appl, 2008, 428: 715-731.

[5] WANG Longqin, MIAO Zhengke, YAN Chao. Local bases of primitive non-powerful signed digraphs[J].Discrete Math, 2009, 309: 748-754.

[6] 范亞東,苗正科,王慶玲. 帶環(huán)的本原不可冪反對稱帶號有向圖的局部基[J]. 徐州師范大學(xué)學(xué)報:自然科學(xué)版，2009,27(3)：10-13.

FAN Yadong,MIAO Zhengke,WANG Qingling.Local bases of primitive non-powerful anti-symmetric signed digraphs with loops[J].Journal of Xuzhou Normal University:Natural Science Edition,2009,27(3)：10-13.