中圖分類號：O157.5 文獻(xiàn)標(biāo)識碼：A

摘要：本文是對帶有三個圈的不可冪的定號有向圖進(jìn)行了研究，通過分析此圖的特點(diǎn)，綜合運(yùn)用指數(shù)、SSSD途徑對、Frobenius數(shù)的相關(guān)性質(zhì)，給出了有向圖的基。

關(guān)鍵詞：有向圖； 基； SSSD途徑對

Abstract： In the paper，we study the non-powerful signed digraph with three simple cycles. By analyzing this kind of digraphs and using the properties of exponents、SSSD walks、Frobeniusnumber，we obtain the equality cases of the base.

Keywords： signed digraph；base； a pair of SSSD walks

1.引 言

實(shí)數(shù)a的符號記為sgna，當(dāng)a>0，a<0，a=0時，sgna定義為+，-，0。由{+，-，0}中的元組成的矩陣稱為符號模式矩陣，簡稱符號模式[1]。設(shè)A=（aij）是n階符號模式，以v={1，2，...，n}為頂點(diǎn)集，以E={（i，j）|aij≠0}為弧集的有向圖D稱為A的伴隨有向圖，記為D（A）.將D（A）中的每一條?。╥，j）賦予aij得到的圖稱為A的伴隨定號有向圖D（A）。

定義1.1[3]. 若定號有向圖中的兩個途徑W1和W2有相同的起點(diǎn)、終點(diǎn)和長度，但有不同的符號，則稱W1和W2為SSSD途徑對。

定義1.2[2]. 若定號有向圖S不包含SSSD途徑對，則S是可冪的，否則S是不可冪的。

設(shè) a1，...，ak是正整數(shù).定義Frobenius的集合S（a1，...，ak）為S（a1，...，ak）={r1a1 +...+rkak|r1，...，rk是非負(fù)整數(shù)}[4]。若g.c.d.（a1，...，ak）=1，則S（a1，...，ak）包含所有足夠大的非負(fù)整數(shù)，定義Frobenius數(shù)φ（a1，...，ak）為對于所有整數(shù)m≥φ都有使得m∈S（a1，...，ak）成立的最小正整數(shù)φ.故φ（a1，...，ak）-1不屬于S（a1，...，ak）。若g.c.d.（a，b）=1，則φ（a，b）=（a-1）（b-1）。

S是帶有三個圈的本原不可冪的定號有向圖（見下圖S）。

2.預(yù)備知識

引理2.1[5]. 設(shè)S是本原定號有向圖，S是不可冪的充要條件是S包含長度分別為p1和p2的兩個圈C1和C2滿足下面兩個條件之一

（B1） pi是奇數(shù)，pj是偶數(shù)且有sgn（Cj）=-1（i，j=1，2 且i≠j）；

（B2） p1和p2都是奇數(shù)，且有sgn（C1）=-sgn（C2）.

方便起見，滿足（B1）或（B2）的一對圈C1和C2稱為“異圈對”。若C1和C2是長度分別為p1和p2的異圈對，則閉路W1=p2C1，W2=p1C2有相同的長度p1p2，但符號不同。則

（sgn（C1））p2=-（sgn（C2））p1（2.1）

本原有向圖D的圈長集合R={l1，...，lr），則g.c.d.（l1，...，lr）=1。對于D中的任意兩點(diǎn)x和y，d（x，y）為從x到y(tǒng)的距離。dR（x，y）為從x到y(tǒng)至少接觸圈長li（i=1，...，r）的圈的最短路徑的長度，設(shè)φR{l1，...，lr）為Frobenius數(shù)，則[3]

expD（u）≤φR+maxv∈V（D）dR（u，v）；（2.2）

exp（D）≤φR+maxx，y∈V（D）dR（x，y）.（2.3）

定義2.1[3].設(shè)S是本原不可冪的定號有向圖，則S的模糊指數(shù)r（S）被定義為最小正整數(shù)r，r是S中的SSSD途徑對。

引理2.2[3]. 設(shè)S是本原不可冪的定號有向圖，W1和W2是從點(diǎn)u到點(diǎn)v長為ru，v的SSSD途徑對，d（S）是S的直徑，則

L（S）≤d（S）+ru，v+expS（v）；（2.4）

L（S）≤d（S）+r+exp（S）.（2.5）

3.主要結(jié)果

定理3.1 設(shè)S是n（n≥8）階本原不可冪定號有向圖，D是S的基礎(chǔ)圖，若m=5，則

（1）若S中的兩個n-5圈符號不同，則L（S）=n2-11n+36.

（2）若S中的兩個n-5圈符號相同，則L（S）=2n2-23n+71.

證明 （1） 設(shè)

Q1=（n-5，n-4）+（n-4，n-3）+（n-3，n-2）+（n-2，n-1）+（n-1，n）+（n，6）

Q2=（n-5，1）+（1，2）+（2，3）+（3，4）+（4，5）+（5，6）

是兩條從n-5到6的6長途徑，則sgnQ1=-sgnQ2，故r（S）≤6.由（2.3）和引理2.2得d（S）=n-7，exp（S）≤φ（n-5，n-6）+maxx，y∈V（D）dR（x，y）≤（n-6）（n-7）+n-5=n2-12n+37.

故L（S）≤d（S）+r+exp（S）≤n-7+6+n2-12n+37=n2-11n+36.

下面證明不存在從n-3到9長為k=n2-11n+35的SSSD途徑對。設(shè)W1和W2是兩條從n-3到9長為k的途徑，P是從n-3到9長為6的最短途徑，W1（或W2）是路徑P和圈Cn-5和Cn-6的連接，則有 k=l（Wi）=ai（n-5）+bi（n-6）+6（ai≥0，bi≥1）（i=1，2）.所以（b2-b1）（n-6）=（a1-a2）（n-5），若a1-a2=（n-6）x，則b2-b1=（n-5）x.

若x≥1 ，則b2≥n-2，所以k=a2（n-5）+b2（n-6）+6=a2（n-5）+（b2-2）（n-6）+2n-6.又因S是本原不可冪，由引理2.1知S中的兩個n-5圈必有一個與n-6圈形成異圈對，則g.c.d.（n-5，n-6）=1，所以φ（n-5，n-6）-1=k-2n+6=a2（n-5）+（b2-2）（n-6）∈S（n-5，n-6）.和Frobenius數(shù)φ（n-5，n-6）的定義矛盾。

同理若x≤-1，也得出矛盾。則x=0，所以a1=a2，b1=b2且sgn（W1）=sgn（W2），因此L（S）≥n2-11n+36.故L（S）=n2-11n+36。

（2）若S中的兩個n-5圈符號相同，則sgnQ1=sgnQ2，又因為S是本原不可冪，由引理2.1知S中的兩個n-5圈必有一個與n-6圈形成異圈對，由（2.1）知（n-6）Cn-5和（n-5）Cn-6的符號不同。

設(shè)P1=（n-5，n-4）+（n-4，n-3）+（n-3，n-2）+（n-2，n-1）+（n-1，n）+（n，6）和P2=（n-5，n-4）+（n-4，n-3）+（n-3，4）+（4，5）+（5，6）是從n-5到6長分別為6和5的途徑，P=（6，7）+…+（n-6，n-5）是從6到n-5長為n-11的途徑。設(shè)W1=P1+（n-7）Cn-5； W2=P2+（n-6）Cn-6.

則W1+P=（n-6）Cn-5；W2+P=（n-5）Cn-6，所以W1和W2的符號不同且形成長度為n2-12n+41的SSSD途徑對。則有r（S）≤n2-12n+41，故

L（S）≤d（S）+r+exp（S）≤n-7+n2-12n+41+n2-12n+37=2n2-23n+71

如（1）的證明，同樣得出不存在從n-3到7的長度為k=2n2-23n+70的SSSD途徑對。所以L（S）≥2n2-23n+71.故L（S）=2n2-23n+71

參考文獻(xiàn)：

[1]Zhongshan Li，F(xiàn)rank Hall，and Carolyn Eschenbach，On the period and base of a sign pattern matrix，Linear Algebra Appl.212/213（1994），pp.101-120.

[2]Lihua You，Jiayu Shao and Haiying Shan，Bounds on the bases of irreducible generalized sign pattern matrices，Linear Algebra Appl.427（2007），pp.285-300.

[3]Bolian Liu and Lihua You，Bound on the base of primitive nearly reducible sign pattern matrices.Linear Algebra Appl.418（2006），pp.863-881.

[4]Yubin Gao，Yanling Shao ang Jian Shen，Bounds on the local bases of primitive nonpowerful nearly reducible sign patterns， Linear and Multilinear Algebra（2008），pp.1-11，iFirst.

[5]Longqin Wang，Zhengke Miao and Chao Yan， Local bases of primitive nonpowerful signed digraphs ，Discrete Mathematics（2008），pp.1-7.