羅美金

(河池學(xué)院數(shù)學(xué)系，廣西宜州 546300)

0 引言

設(shè)D是一個有向圖，D的一條長為l的途徑是指連續(xù)的頂點(diǎn)序列v1，v2，…，vl+1，其中對所有的i=1，2，…，l，D 中有從 vi到 vi+1的?。绻?v1，v2，…，vl+1互不相同，則稱該途徑是一條長為 l的路．如果 v1=vl+1，則稱為一條閉路或圈．如果D是包含紅弧和藍(lán)弧的有向圖，則稱D是一個雙色有向圖．雙色有向圖D是強(qiáng)連通的，如果D中每一對頂點(diǎn)(i，j)都存在從i到j(luò)的途徑．給定D中的一條途徑ω，用r(ω)和b(ω)－分別表示ω中紅弧和藍(lán)弧的條數(shù)，稱 ω 為一條(r(ω)，b(ω))途徑，ω 的分解為向量(r(ω)，b(ω))或(r(ω)，b(ω))T．

一個雙色有向圖D是本原的，當(dāng)且僅當(dāng)存在非負(fù)整數(shù)h和k，且h+k＞0，使得D中的每一對頂點(diǎn)(i，j)都存在從i到j(luò)的(h，k)－途徑，h+k的最小值定義為雙色有向圖D的本原指數(shù)，記為exp(D)．

設(shè)C={γ1，γ2，…，γl}是D的圈的集合，定義D的圈矩陣M是一個2×l矩陣，它的第i列是γi的分解．M的content(記為content(M))定義為0如果M的秩小于2，否則定義為M的所有非零2階主子式的最大公因數(shù)．

引理1［1］一個至少包含一條紅弧和一條藍(lán)弧的雙色有向圖D是本原的，當(dāng)且僅當(dāng)D是強(qiáng)連通的，且content(M)=1．

雙色有向圖和非負(fù)矩陣對之間存在一一對應(yīng)關(guān)系，近幾年對本原雙色有向圖本原指數(shù)的研究已經(jīng)取得了一些重要成果，見文獻(xiàn)［1－6］．本文研究了一類特殊的雙色有向圖D，它的未著色有向圖如圖1所示．

圖1 D的未著色有向圖

其中a，b為正整數(shù)．

1 本原條件

以下分兩種類型討論雙色有向圖D的本原指數(shù):

2 指數(shù)界

定理2 設(shè)雙色有向圖D是本原的，且屬于類型1，則

設(shè)存在一對非負(fù)整數(shù)(h，k)，使對D中所有頂點(diǎn)對(i，j)，都有一條從i到j(luò)的(h，k)－途徑．取i=j=n+1，則存在非負(fù)整數(shù)u和v，有

有非負(fù)整數(shù)解，即

或

有非負(fù)整數(shù)解，即

所以 v≥n－2．

再證exp(D)≤2n2+3n．

只需證明D的任意一對頂點(diǎn)(i，j)，都有一條(n2－n，4n)－途徑．對D中的任意一對頂點(diǎn)(i，j)，記pij是從 i到 j的最短路，r(pij)=s，b(pij)=t．可得，

考慮以下兩種情況:

情況2:pij包含)－圈上的頂點(diǎn)．此時，0≤s≤n－1，0≤t≤2．

a)若 t=0，則0≤s≤n－1;b)若 t=1，則 0≤s≤n－1;c)若 t=2，則0≤s≤n－2．

綜上所述，exp(D)≤2n2+3n．定理得證．

類似定理2的證明，可得定理3．

定理3 設(shè)雙色有向圖D是本原的，且屬于類型2，則

3 極圖刻劃

考慮以下兩種情況:

情況2:pij包含－圈上的頂點(diǎn)．此時，0≤s+t≤n－1．

結(jié)合定理 2、3、4，同理，類似可證得定理 5、6、7．

定理5 設(shè)雙色有向圖D是本原的，且屬于類型2，則exp(D)=2n2+3n，當(dāng)且僅當(dāng)弧或弧n+1→1→2是藍(lán)色的，其它弧是紅色的．

［1］Shader B L，Suwilo S．Exponents of nonnegative matrix pairs［J］．Linear Algebra Appl．，2003，363:275－293．

［2］SHAO Yanling，GAO Yubin，SUN Liang．Exponent of a class of two－colored digraphs［J］．Linear and Multilinear Algrbra，2005，53(3):175－188．

［3］羅美金，高玉斌．一類恰含三個圈的三色有向圖的本原指數(shù)［J］．山東大學(xué)學(xué)報(理學(xué)版)，2008，43(1):65－72．

［4］羅美金，高玉斌．一類雙色有向圖的本原指數(shù)［J］．中北大學(xué)學(xué)報(自然科學(xué)版)，2008，29(2):95－100．

［5］GAO Yubin，SHAO Yanling．Exponent of two－colored double directed cycles［J］．Journal of Natural Science of Heilongjiang University，2004(4):55－58．

［6］白竹香，邵燕靈．一類雙色有向圖的指數(shù)［J］．中北大學(xué)學(xué)報(自然科學(xué)版)，2007，28(2):100－103．