某類本原不可冪定號(hào)有向圖的基指數(shù)

趙 晶,高玉斌

(中北大學(xué)理學(xué)院,山西太原030051)

1 問題的提出

一個(gè)實(shí)數(shù) a的符號(hào)sgn a根據(jù)a＞0,a＜0或 a=0,被定義為1,-1或0.將一個(gè)有向圖D(允許含有環(huán)但不能有重弧)中的每一條弧賦予符號(hào)1或-1所得的圖稱為D的定號(hào)有向圖.定號(hào)有向圖中的一條途徑W是由一系列的弧e1,e2,…,ek組成的,并且ei的終點(diǎn)與ei+1的起點(diǎn)相同 (i=1,Λ,κ-1).途徑W中所含弧的條數(shù)稱為途徑W的長(zhǎng)度,記為l(W)[1].途徑W的符號(hào)定義為W中所有弧的符號(hào)的乘積(重復(fù)出現(xiàn)的弧的符號(hào)重復(fù)計(jì)),即

設(shè) D為有向圖,如果存在正整數(shù) k,使得對(duì)于 D中的任意頂點(diǎn)νi和νj(可以相同)都有從νi到νj的長(zhǎng)為k的途徑,則稱D為本原的,滿足上述條件的最小的k被稱為D的本原指數(shù),記為exp(D)[3].設(shè)D是一個(gè)本原有向圖,對(duì)于νi∈D,存在正整數(shù) p,使得對(duì)任意t≥p,從頂點(diǎn)νi到D中的任一點(diǎn)都有長(zhǎng)為t的途徑,滿足上述條件的最小正整數(shù) p,叫做頂點(diǎn)νi的點(diǎn)指數(shù),記為expD(νi)[4].設(shè)S是一個(gè)本原不可冪定號(hào)有向圖,使得對(duì)任意正整數(shù) t≥l,及 S中任意兩個(gè)頂點(diǎn)νi和νj(可以相同),從νi到νj都有長(zhǎng)為t的SSSD途徑對(duì),則稱滿足上述條件的最小正整數(shù)l是定號(hào)有向圖S的基,記為l(S)[5].

定義1.1[6]定號(hào)有向圖中的兩條途徑W1和W2,如果它們有相同的起點(diǎn)、終點(diǎn)、長(zhǎng)度,但有不同的符號(hào),則稱為SSSD途徑對(duì).

定義1.2[7]如果定號(hào)有向圖S不包含SSSD途徑對(duì),則稱S為可冪的,否則稱S為不可冪的.

2 預(yù)備知識(shí)

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

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

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

為了方便,稱滿足 (Ⅰ)或 (Ⅱ)的圈對(duì) C1和 C2為“異圈對(duì)”.容易看到閉圈對(duì)W1=p2C1和W2=p1C2有相同的長(zhǎng)度 p1p2,但有不同的符號(hào):

設(shè) a1,…,ak都為正整數(shù),定義Frobenius集S(a1,…,ak)={r1a1+…+rkak|r1,…,rk都是非負(fù)整數(shù)}.根據(jù)Schur引理,如果 g.c.d(a1,…,ak)=1,那么 S(a1,…,ak)包含足夠大的非負(fù)整數(shù).在這種情況下,定義Frobenius數(shù)φ(a1,…,ak)為對(duì)于所有整數(shù)m≥φ,使得m∈S(a1,…,ak)成立的最小整數(shù)φ.根據(jù)上面的定義,有φ(a1,…,ak)-1?S(a1,…,ak).另外,如果 a,b是互素的非負(fù)整數(shù),那么

設(shè)R={l1,…,lk}是本原有向圖D中圈長(zhǎng)的集合,且 g.c.d(l1,…,lk)=1.對(duì)于 D中的每個(gè)頂點(diǎn)x和頂點(diǎn)y,用 d(x,y)表示從 x到y(tǒng)的距離,dR(x,y)(關(guān)于集合 R,從 x到y(tǒng)的相對(duì)距離)為從 x到y(tǒng)至少接觸長(zhǎng)為li(對(duì)于每個(gè) i=1,…,r)的一個(gè)圈的最短途徑的長(zhǎng)度.記 φR=φ(l1,…lk)為Frobenius數(shù),則對(duì)于本原指數(shù)和點(diǎn)指數(shù)有以下式子成立:

引理 2.2[10]設(shè)S是一個(gè)本原不可冪定號(hào)有向圖,W1與W2是從點(diǎn)u到ν的長(zhǎng)度為r的SSSD途徑對(duì),d(S)表示S的直徑,則有以下不等式成立:

本文主要對(duì)一類本原不可冪定號(hào)有向圖S進(jìn)行研究,其基礎(chǔ)圖D為以下圖1所示.顯然,D包含3個(gè)圈,其中兩個(gè)圈長(zhǎng)相等為n-3,另一個(gè)圈長(zhǎng)為n-1.通過研究得出如下主要結(jié)果.

3 主要結(jié)論

定理 3.1 設(shè) S是一個(gè)n(n≥7)階本原不可冪定號(hào)有向圖,其基礎(chǔ)圖為 D(如圖1所示).則

(Ⅰ)若S中的兩個(gè) n-3圈異號(hào),則 l(S)=n2-4n+5.

(Ⅱ)若S中的兩個(gè)n-3圈同號(hào),則l(S)=2n2-9n+11.

證明 (Ⅰ)若 S中的兩個(gè)n-3圈異號(hào),令 Q1=(νn-2,ν2)+(ν2,ν3),Q2=(νn-2,νn)+(νn,ν3) 分別是從νn-2到ν3的長(zhǎng)度為2的兩條途徑.另外,R={n-3,n-1},分別用 Cn-1,Cn-3表示 n -1圈與 n -3的圈.由并結(jié)合 ( 2 ),(3) 得expD(ν3)≤φ(n-1,n-3)+n-3=n2-5n+5. 根據(jù) (4) 得 l (S)≤d(S)+r+exps(ν)≤n-2+2+n2-5n+5=n2-4n+5.接下來用反證法證明l(S)≥n2-4n+5,即證明從ν1到νn-1不存在長(zhǎng)為 n2-4n+4的SSSD途徑對(duì).假設(shè)Wi(i=1,2)是任意兩條從ν1到νn-1的長(zhǎng)為 k =n2-4n+4的途徑,顯然,n2-4n+4≥1,即每個(gè)Wi至少要繞Cn-1一圈,且由若干個(gè) Cn-1圈和 Cn-3圈組成.所以,存在非負(fù)整數(shù) ai,bi,使得

圖1 定號(hào)有向圖 S的基礎(chǔ)圖D

與 φ(n-1,n-3)定義矛盾.

因此,a1=a2,b1=b2,即sgn W1=sgn W2.由此證得從ν1到νn-1不存在長(zhǎng)為 k的SSSD途徑對(duì).

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

(Ⅱ)若S中的兩個(gè)n-3圈同號(hào),即 sgn Q1=sgn Q2.令 Q是從ν3到νn-2的長(zhǎng)為 n-5的唯一途徑.再令 P1=(νn-2,νn-1)+(νn-1,ν1)+(ν1,ν2)+(ν2,ν3),P2=(νn-2,ν2)+(ν2,ν3) 分別是從νn-2到ν3的長(zhǎng)為4與2的途徑.

由于S是本原不可冪的定號(hào)有向圖,且S中僅有的3個(gè)圈是由兩個(gè)圈n-3和一個(gè)n-1圈組成,根據(jù)引理2.1知,每個(gè)n-3圈與n-1圈都可以構(gòu)成一個(gè)“異圈對(duì)”.則由 (1)易知 (n-1)Cn-3與 (n-3)Cn-1符號(hào)相反.因此,令W1=P1+(n-4)Cn-1,W2=P2+(n-2)Cn-3分別是從νn-2到ν3的長(zhǎng)為 n2-5n+8的途徑對(duì).從而W1+Q=(n-3)Cn-1,W2+Q=(n-1)Cn-3,即有W1與W2符號(hào)相反.由此得出,W1與W2是一對(duì)從νn-2到ν3的長(zhǎng)為 n2-5n+8的 SSSD途徑對(duì).接下來的證明類似 (Ⅰ)中證明,由(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不存在長(zhǎng)為 k=2n2-9n+10的 SSSD途徑對(duì).假設(shè)Wi(i=1,2)是任意兩條從ν1到ν2的長(zhǎng)為 k=2n2-9n+10的 SSSD途徑對(duì),容易看出2n2-9n+10≥1,則每個(gè)Wi都由若干個(gè)Cn-1圈和若干個(gè) Cn-3圈組成,且至少要繞 Cn-1一圈.所以,存在非負(fù)整數(shù) ai,bi,使得 k=l(Wi)=1+ai(n-1)+bi(n-3)(ai≥1,bi≥0),故有 (a2-a1)(n-1)=(b1-b2)(n-3).設(shè) 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不存在長(zhǎng)為 k的SSSD途徑對(duì).

綜上得出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