一類特殊雙色有向圖的指數界

羅美金

(河池學院數學系，廣西宜州 546300)

0 引言

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

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

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

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

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

圖1 D的未著色有向圖

其中a，b為正整數．

1 本原條件

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

2 指數界

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

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

有非負整數解，即

或

有非負整數解，即

所以 v≥n－2．

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

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

考慮以下兩種情況:

情況2:pij包含)－圈上的頂點．此時，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 設雙色有向圖D是本原的，且屬于類型2，則

3 極圖刻劃

考慮以下兩種情況:

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

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

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

［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］羅美金，高玉斌．一類恰含三個圈的三色有向圖的本原指數［J］．山東大學學報(理學版)，2008，43(1):65－72．

［4］羅美金，高玉斌．一類雙色有向圖的本原指數［J］．中北大學學報(自然科學版)，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］白竹香，邵燕靈．一類雙色有向圖的指數［J］．中北大學學報(自然科學版)，2007，28(2):100－103．