兩類特殊本原不可冪定號有向圖基的界

王慧敏,邵燕靈

(中北大學(xué)數(shù)學(xué)系,山西太原030051)

兩類特殊本原不可冪定號有向圖基的界

王慧敏,邵燕靈

(中北大學(xué)數(shù)學(xué)系,山西太原030051)

為了進(jìn)一步了解本原不可冪定號有向圖基的相關(guān)性質(zhì),對兩類含有四個圈的本原不可冪定號有向圖的基進(jìn)行了研究.利用有關(guān)本原不可冪定號有向圖的引理及定義,并分析有向圖的性質(zhì),綜合運用指數(shù)、SSSD途徑對和圖的直徑分別求其上、下界,從而得到了兩類有向圖基的界.若上界與下界相等,則可得到其基的具體值.

不可冪;本原指數(shù);基;定號有向圖;SSSD途徑對

1 引 言

有關(guān)定號有向圖基的研究,目前取得了一些結(jié)果.文獻(xiàn) [2]中討論了本原不可冪定號對稱有向圖(含自環(huán))的基;文獻(xiàn) [3]中作者介紹了可約符號模式矩陣周期與基;文獻(xiàn) [4]中作者介紹了不可約廣義符號模式矩陣基的界;文獻(xiàn) [5]中給出了幾乎可約符號模式矩陣基的界.下面是有關(guān)基的一些定義.

設(shè)A=(aij)是一個n階符號模式矩陣,A的伴隨有向圖D(A) (可能含有環(huán))是指一個有向圖,它包含點集V={1,2,…n}和弧集 E={(i,j)|aij≠0}.按照A中aij的符號,將D(A)中的每一條弧定義一個符號1或-1所得的圖稱為D(A)的定號有向圖,記為S(A),S(A)為A的伴隨定號有向圖,即D(A)就成為S(A)的基礎(chǔ)有向圖.

設(shè)S為一個定號有向圖,S中的一條途徑W是一個有關(guān)弧的序列:e1,e2,…,ek,使得ei的終點與ei+1的起點相同,其中i=1,2,…,k-1.所含弧的條數(shù) k即是途徑W的長度,記為l(W).途徑W的符號被定義為 記為sgn(W).如果一個定號有向圖中的兩條途徑W1和W2有相同的起點和相同的終點及相同的長度,但是符號相反,則稱它們?yōu)橐粋€SSSD途徑對[1].

定義1.1 設(shè)D為有向圖,如果存在正整數(shù)l,使得對于D的任意頂點νi,νj(可以相同),在D中都存在從νi到νj長為l的途徑,則稱 D為本原有向圖.上述最小的 l稱為D的本原指數(shù),記為exp(D).

定義1.2 設(shè) D是一個本原有向圖,νi∈V(D),存在正整數(shù) p,若對任意的 t≥p,從頂點νi到D中的任一點都有長為t的途徑,滿足上述條件的最小正整數(shù) p,就叫做頂點νi的點指數(shù),記為expD(νi).

定義1.3 設(shè) S是一個本原不可冪定號有向圖,若對任意頂點νi和νj(可以相同),并且對任意 t≥l,從νi到νj都有長為t的SSSD途徑,則稱滿足上述條件的最小正整數(shù) l,就叫做 S的基,記為 l(S).

定義1.4[1]如果定號有向圖S中不包含SSSD途徑對,則稱S為可冪的,否則稱S為不可冪的.

定義1.5 設(shè)S是一個本原不可冪定號有向圖,S的歧義指數(shù) (ambiguous index)被定義為S中最短的SSSD途徑對的長度,記為 r(S).用 ru,ν表示從頂點u到頂點ν的最短的SSSD途徑對的長度.

2 預(yù)備知識

引理2.1[5]設(shè)S是一個本原定號有向圖,則 S不可冪當(dāng)且僅當(dāng)S中存在兩個不同的圈C1,C2(其長分別為 p1和 p2)滿足下面兩個條件之一:

(Ⅰ)p1是奇數(shù),p2是偶數(shù),并且有sgnC2=-1;

(Ⅱ)p1和 p2都是奇數(shù),并且有sgnC1=-sgnC2.

為了方便,稱滿足 (Ⅰ)或 (Ⅱ)的圈對 C1和 C2為“異圈對”.容易看到若 C1和 C2是長分別為 p1和 p2的異圈對,則閉圈對W1=p2C1和W2=p1C2有相同的長度 p1p2,但有不同的符號:

設(shè) a1,…,ak都為正整數(shù).Frobenius集S(a1,…,ak)定義如下:

根據(jù)Schur引理,如果 g.c.d(a1,…,ak)=1,那么S(a1,…,ak)包括足夠大的正整數(shù).在這種情況下,使得所有 m≥φ的整數(shù)m∈S(a1,…,ak)的最小整數(shù)φ,稱為Frobenius數(shù)φ(a1,…,ak).

根據(jù)上面的定義,則有φ(a1,…,ak)-1?S(a1,…,ak).如果 a,b是互素的兩個正整數(shù),則有

設(shè)R={l1,…,lk}是本原有向圖D中圈長的集合,且 g.c.d(l1,…,lk)=1.對于 D中的每個頂點x和頂點y,用 d(x,y)表示從 x到y(tǒng)的距離,dR(x,y)表示從 x到y(tǒng)接觸R中每一長度的圈的最小距離.用φR=φ(l1,…lk)表示Frobenius數(shù),則對于本原指數(shù)和點指數(shù)有以下式子成立:

引理2.2[5]設(shè)S是一個n階本原不可冪定號有向圖,其基礎(chǔ)圖為 D.d(S)表示 S的直徑,W1和W2為從頂點 u到頂點ν的長度為ru,ν的SSSD途徑對.則

本文主要是對基礎(chǔ)圖是D1、D2的本原不可冪定號有向圖 S1、S2進(jìn)行研究,得到了不同情況下有向圖的基或基的界.

圖1 定號有向圖 S1的基礎(chǔ)圖 D1

圖2 定號有向圖 S2的基礎(chǔ)圖 D2

3 結(jié) 論

定理3.1 設(shè) S1是 n(nφ8,n≠8+3x)(其中 x為正整數(shù))階本原不可冪定號有向圖,D1是它的基礎(chǔ)圖,則

(Ⅰ)如果 S1中的兩個 n-2圈具有不同的符號,則 l(S1)≤n2-7n+17.

(Ⅱ)如果S1中的兩個n-5圈具有不同的符號,則l(S1)=n2-7n+12.

(Ⅲ)如果S1中的兩個n-2圈具有相同的符號,且兩個n-5圈也具有相同的符號,則l(S1)=2n2-15n+27.

證明 在圖S1中,記 R={n-5,n-2},且 d(S1) =n-1.

(Ⅰ) 令 Q1=(νn-4,νn-3)+(νn-3,νn-2)+(νn-2,ν1) 和 Q2=(νn-4,νn-1)+(νn-1,νn)+(νn,ν1) 是從νn-4到ν1的長為3的兩條路徑.由于 S1中的 (僅有的)兩個 n-2圈具有不同的符號,則一定有sgnQ1=-sgnQ2, 故 rνn-4,ν1≤3, 又u)≤n-3,由公式 (1) 和 (3) 得

再由公式 (4)得

即定理3.1的 (Ⅰ)得證.

(Ⅱ) 令 Q1=(νn-5,ν1)+(ν1,ν2) 和 Q2=(νn-5,νn-4)+(νn-4,ν2) 是從νn-5到ν2的長為 2 的兩條路徑.由于 S1中的 (僅有的)兩個 n-5圈具有不同的符號,則一定有sgnQ1=-sgnQ2,故又由于≤n-4,由公式 (1) 和 (3) 得

對任意的νi,νj∈V(D),從νi到νn-5的路徑的長度 d≤n-4.又由于ν2在兩個 Cn-5上,可知對任意的 t≥n2-8n+14,存在從ν2到νj的一條t長途徑,那么就存在一對從νi到νj的長度為d+2+n2-8n+14+n-4-d=n2-7n+12的SSSD途徑對.所以可得

接下來證明l(S1)≥n2-7n+12.用反證法,證明從νn-1到νn無長為k=n2-7n+11的SSSD途徑對.

設(shè)W1和W2是任意兩條從νn-1到νn的長為k的途徑,那么每個Wi(i=1,2)是由從νn-1到νn長為1的路徑和若干個 (至少一個)Cn-2圈和Cn-5圈組成 (其中Cn-2,Cn-5分別表示長度為n-2和n-5的圈).即 k=l(Wi)=n2-7n+11=ai(n-2)+bi(n-5)+1+n-2(ai≥0,bi≥0),就有 (ai+1) (n-2)=(n-2-bi)(n-5).可知要使等式成立,一定有bi=n-2,0.由于bi=n-2時,ai=-1與 ai≥0矛盾,故bi=0成立,此時 ai=n-6.即兩個任意從νn-1到νn的長為k的途徑都只繞Cn-2,不繞 Cn-5,則 sgn(W1)=sgn(W2).所以S1中不存在長為k的SSSD途徑對,從以上討論中可得

綜合 (7)和 (8),得l(S1)=n2-7n+12.即定理3.1的 (Ⅱ)得證.

(Ⅲ)在圖 S1中,如果S1中的 (僅有的)兩個 n-2圈具有相同的符號,且 (僅有的)兩個 n-5圈也具有相同的符號,則sgnQ1=sgnQ2.由于圖S1是本原不可冪的,且圖S1中僅有兩個n-2圈和兩個 n-5圈,由引理2.1知:每一個 n-2圈與一個 n-5圈都可以構(gòu)成一對“異圈對”.所以 (n-2)Cn-5和(n-5)Cn-2有不同的符號 (其中 Cn-2表示由 (νn-4,νn-3,νn-2, …,νn-5)組成的 n-2圈,Cn-5表示由(Vn-4,ν2, …νn-6,νn-5) 組成的 n-5 圈). 令 P1=(νn-4,νn-3)+(νn-3,νn-2)+(νn-2,ν1)+(ν1,ν2)和 P2=(νn-4,ν2) 分別是從νn-4到ν2的長為 4 和 1 的兩條路徑. P=(ν2,ν3)+ …+(νn-6,νn-5)+(νn-5,νn-4)是從ν2到νn-4的唯一路徑.再令W1=P1+(n-6) Cn-2,W2=P2+(n-3)Cn-5是從νn-4到ν2的長為 n2-8n+16的途徑對,那么就有W1+P=(n-5)Cn-2,W2+P=(n-2)Cn-5.因 (n-5)Cn-2和 (n-2)Cn-5有不同的符號,故 W1與 W2也有不同的符號,從而 W1與W2為一對從νn-4到ν2長為 n2-8n+16的SSSD途徑對,所以 rνn-4,ν2≤n2-8n+16. 對任意的νi,νj∈V(D),從νi到νn-4的路徑的長度 d≤n-3.又由于ν2是所有圈的公共點,再由 (6)可知,對任意的 t≥n2-8n+14存在從ν2到νj的一條t長途徑.那么就存在一對從νi到νj的長度為d+n2-8n+16+n2-8n+14+n-3-d=2n2-15n+27的 SSSD途徑對.所以可得

接下來證明l(S1)≥2n2-15n+27.用反證法,證明從νn-1到νn無長為k=2n2-15n+26的 SSSD途徑對.

設(shè)W1和Ww是任意兩條從νn-1到νn的長為k的途徑,那么每個Wi(i=1,2)是由從νn-1到νn長為1的路徑和若干個 (至少一個)Cn-2圈和若干個 Cn-5圈組成.即 k=l(Wi)=ai(n-2)+bi(n-5)+1(ai≥1,bi≥0),故有:(a2-a1)(n-2)=(b1-b2)(n-5).設(shè)b1-b2=(n-2)x,那么 a2-a1=(n-5)x.下面證明 x=0,用反證法:如果 x≥1,則 a2≥a1+n-5≥n-4(由于 a1≥1),所以 k=[a2-(n-4)](n-2)+b2(n-5)+1+(n-4)(n-2).則有 φ(n-2,n-5)-1=(n-3)(n-6)-1=k-[1+(n-4)(n-2)]=[a2-(n-4)](n-2)+b2(n-5)∈S(n-2,n-5)與Frobenius數(shù)φ(n-2,n-5)的定義矛盾.同理可證 x≤-1也與Frobenius數(shù)φ(n-2,n-5)的定義矛盾.所以 x=0成立,即有a1=a2,b1=b2.那么sgnQ1=sgnQ2,所以S1中不存在長為k的SSSD途徑對.從以上討論證明中可得到

綜合 (9)和 (10),得l(S1)=2n2-15n+27.定理3.1得證.

定理3.2 設(shè) S2是 n(s≥2,n≥s+5)(其中s為正整數(shù))階本原不可冪定號有向圖,D2是它的基礎(chǔ)圖,則

(Ⅰ)如果S2中的兩個n-2圈具有不同的符號,則l(S2)=n2-5n+8

(Ⅱ)如果S2中的兩個n-3圈具有不同的符號,則l(S2)=n2-5n+6

(Ⅲ)如果S2中的兩個n-2圈具有相同的符號,且兩個n-3圈也具有相同的符號,則l(S2)=2n2-11n+17.

證明 在圖S2中,記 R={n-2,n-3},且 d(S2)=n-2.

(Ⅰ) 令 Q1=(νs,νs+1)+(νs+1,νs+3) 和 Q2=(νs,νs+2)+(νs+2,νs+3) 是從νs到νs+3的長為 2 的兩條路徑.由于 S2中的 (僅有的)兩個 n-2圈具有不同的符號,則一定有 sgnQ1=-sgnQ2,故 rνs,νs+3≤2,u)≤n-4,由公式 (1) 和 (3) 得

再由公式 (4)得

接下來證明l(S2)≥n2-5n+8.用反證法,證明從νn-1到νn無長為k=n2-5n+7的 SSSD途徑對.

設(shè)W1和W2是任意兩條從νn-1到νn的長為k的途徑,那么每個Wi(i=1,2)是由從νn-1到νn長為1的路徑和若干個 (至少一個)Cn-2圈和Cn-3圈組成 (其中Cn-2,Cn-3分別表示長度為n-2和n-3的圈).即 k=l(Wi)=n2-5n+7=ai(n-2)+bi(n-3)+1+n-2(ai≥0,bi≥0),就有 (ai+1)(n-2)=(n-2-bi)(n-3).可知要使等式成立,一定有bi=n-2,0.由于bi=n-2時,ai=-1與 ai≥0矛盾,故bi=0成立,此時 ai=n-4.即兩個任意從νn-1到νn的長為k的途徑都只繞Cn-2,不繞 Cn-3,則sgn(W1)=sgn(W2).所以S2中不存在長為k的SSSD途徑對,從以上討論中可得

綜合 (12)和 (13),得l(S2)=n2-5n+8.即定理3.2的 (1)得證.

(Ⅱ)由于S2中的 (僅有的)兩個n-3圈具有不同的符號,則一定有sgnQ1=-sgnQ2,由于在同一個圖中且有相同的路徑,可得 (11).對任意的νi,νj∈V(D),從νi到νs的路徑的長度d≤n-4.又由于νs+3在兩個 Cn-3上,可知對任意的t≥n2-6n+8,存在從νs+3到νj的一條t長途徑,那么就存在一對從νi到νj的長度為d+2+n2-6n+8+n-4-d=n2-5n+6的SSSD途徑對.所以可得

接下來證明l(S2)≥n2-5n+6.用反證法,證明從νn-2到νn-2無長為 k=n2-5n+5的 SSSD途徑對.

設(shè)W1和W2是任意兩條從νn-2到νn-2的長為 k的途徑,那么每個Wi(i=1,2)是由若干個 Cn-2圈和Cn-3圈 (至少一個)組成.即 k=l(Wi)=n2-5n+5=ai(n-2)+bi(n-3)+n-3(ai≥0,bi≥0),就有(ai+1)(n-2)=(n-2-bi)(n-3).以下同定理3.2(1)的證明,所以可得

綜合 (14)和 (15),得l(S2)=n2-5n+6.即定理3.2的 (2)得證.

(Ⅲ)在 S2中,如果 S2中的 (僅有的)兩個 n-2圈具有相同的符號,且 (僅有的)兩個 n-3圈也具有相同的符號,則sgnQ1=sgnQ2.由于S2是本原不可冪的,且S2中僅有兩個n-2圈和兩個n-3圈,由引理2.1知:每一個n-2圈與一個 n-3圈都可以構(gòu)成一對“異圈對”.所以 (n-2)Cn-3和 (n-3)Cn-2有不同的符號 (其中 Cn-2表示由 (ν1,ν2, …,νs,νs+1,νs+3, …,νn-3,νn-1,νn) 組成的 n-2圈,Cn-3表示由 (ν1,ν2, …,νs,νs+1,νs+3, …,νn-3,νn-2組成的 n-3圈).

令 P1=(νn-3,νn-1)+(νn-1,νn)+(νn,ν1) 和 P2=(νn-3,νn-2)+(νn-2,ν1) 分別是從νn-3到ν1的長為 3 和 2 的兩條路徑. P=(ν1,ν2)+ …+(νs,νs+1)+(νs+1,νs+3)+ …+(νn-4,νn-3) 是從ν1到νn-3的唯一路徑.再令W1=P1+(n-4)Cn-2,W2=P2+(n-3)Cn-3是從νn-3到ν1的長為 n2-6n+11的途徑對,那么就有W1+P=(n-3)Cn-2,W2+P=(n-2)Cn-3.因 (n-3)Cn-2和 (n-2)Cn-3有不同的符號,故W1與W2也有不同的符號,從而W1與W2為一對從νn-3到ν1長為 n2-6n+11的 SSSD途徑對,所以rνn-3,ν1≤n2-6n+11. 又2≤n-3,由公式 (1) 和 (3) 得

對任意的νi,νj∈V(D),從νi到νn-3的路徑的長度 d≤n-3.又由于ν1是所有圈的公共點,再由(16)可知,對任意的t≥n2-6n+9存在從ν1到νj的一條t長途徑.那么就存在一對從νi到νj的長度為d+n2-6n+11+n2-6n+9+n-3-d=2n2-11n+17的SSSD途徑對.所以可得

接下來證明l(S2)≥2n2-11n+17.用反證法,證明從νn-1到νn無長為k=2n2-11n+16的 SSSD途徑對.

設(shè)W1和W2是任意兩條從νn-1到νn的長為k的途徑,那么每個Wi(i=1,2)是由從νn-1到νn長為1的路徑和若干個 (至少一個)Cn-2圈和若干個 Cn-3圈組成.即 k=l(Wi)=ai(n-2)+bi(n-3)+1(ai≥1,bi≥0),故有:(a2-a1)(n-2)=(b1-b2)(n-3).設(shè) b1-b2=(n-2) x,那么 a2-a1=(n-3) x.下面證明 x=0,用反證法:如果 x≥1,則 a2≥a1+n-3≥n-2(由于 a1≥1),所以 k=[a2-(n-2)](n-2)+b2(n-3)+1+(n-2)2.則有 φ(n-2,n-3)-1=(n-3)(n-4)-1=k-[1+(n-2)2=[a2-(n-2)](n-2)+b2(n-3)∈S(n-2,n-3)與Frobenius數(shù)φ(n-2,n-3)的定義矛盾.同理可證 x≤-1也與Frobenius數(shù)φ(n-2,n-3)的定義矛盾.所以 x=0成立,即有 a1=a2,b1=b2.那么sgnQ1=sgnQ2,所以S1中不存在長為k的SSSD途徑對.從以上討論證明中可得到

綜合 (17)和 (18),得l(S2)=2n2-11n+17.定理3.2得證.

[1] Gao YB,Huang YH,Shao YL.Bases of primitive non-powerful singed symmetric digraphs with loops[J].Ars 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,Shao YL.Generalized exponents of primitive two-colored digraphs[J].Linear Algebra Appl,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,Miao ZK,Yan C.Local bases of primitive non-powerful signed digraphs[J].Discr Math,2009,309：748-754

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

[8] Gao YB,Shao YL,Shen J.Bounds on 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 Appl,2009,430：718-731

[10] You L H,Shao J Y,Shan HY.Bounds on the bases of irreducible generalized sign pattern matrices[J].Linear Algebra Appl,2007,427：285-300

Bounds on Bases of Two Special Classes of Primitive Non-powerful Signed Digraphs

WANG Hui-min,SHAO Yan-ling
(College of Science,North University of China,Taiyuan 030051,China)

The bases of two special classes of primitive non-powerful signed digraphs with four simple Coops were studied to research the related properties about primitive non-powerful signed digraphs.Through some lemmas and definition of the primitive non-powerful signed digraphs,and the analysis of the signed digraph,and using the knowledge of primitive exponent,SSSDwalks and the diameter of a digraph,we obtain the bounds on the bases of two special classes of signed digraphs.If the upper bounds are equal with the lower bounds,the specific value of the bases is obtained.

non-powerful;primitive exponent;bases;signed digraph;SSSDwalks

O 157.5

A

1673-1492(2011)04-0001-05

來稿日期：2011-05-10

國家自然科學(xué)基金資助項目 (11071227);山西省自然科學(xué)基金資助項目 (2008011009)

王慧敏(1986-),女,山西晉城人,中北大學(xué)數(shù)學(xué)系在讀研究生.導(dǎo)師：邵燕靈 (1963-),女,教授,博士,博士生導(dǎo)師.

劉守義 英文編輯：劉彥哲]