特殊雙圈雙色有向圖的本原指數(shù)界

羅美金

(河池學(xué)院 數(shù)學(xué)與統(tǒng)計學(xué)院， 廣西 宜州 546300)

n階非負(fù)矩陣對(A,B)與其具有n個頂點(diǎn)的伴隨有向圖D(A,B)存在一一對應(yīng)關(guān)系[1]，即(A,B)中元素的符號和D(A,B)中弧存在與否相對應(yīng)。例如：設(shè)矩陣A=(aij)，B=(bij)，若aij>0(bij>0)，則表示D(A,B)中從頂點(diǎn)i到頂點(diǎn)j存在一條紅弧(藍(lán)弧)；相反，不存在紅弧(藍(lán)弧)。

只含紅弧和藍(lán)弧的有向圖D，稱為一個雙色有向圖[2]。若記exp(A,B)為非負(fù)本原矩陣對(A,B)的本原指數(shù)，exp(D(A,B))為非負(fù)本原矩陣對(A,B)所對應(yīng)的伴隨有向圖(即雙色有向圖)D(A,B)的本原指數(shù)，根據(jù)兩者的對應(yīng)關(guān)系，則有exp(A,B)=exp(D(A,B))。因此，類似非負(fù)矩陣對本原指數(shù)的概念，可定義雙色有向圖的本原指數(shù)的概念為：

若存在非負(fù)整數(shù)h和k，且h+k>0，使得D中的每一對頂點(diǎn)(i,j)都存在從i到j(luò)的(h,k)-途徑，則雙色有向圖D是本原的，且h+k的最小值為雙色有向圖D的本原指數(shù)，記作exp(D)，其中h和k分別表示一條途徑中紅弧和藍(lán)弧的條數(shù)[2]。

設(shè)C={γ1,γ2,…,γl}是D的圈集合，D的圈矩陣為M，若M的秩小于2，則M的content(記為content(M))定義為0，否則定義content(M)為M的所有非零2階主子式的最大公因數(shù)[2]。

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

根據(jù)非負(fù)矩陣對與雙色有向圖的對應(yīng)關(guān)系，通過雙色有向圖本原指數(shù)的研究能得出相應(yīng)非負(fù)矩陣對的本原指數(shù)。近幾年，國內(nèi)外專家、學(xué)者關(guān)于非負(fù)矩陣對本原指數(shù)的研究主要集中在特殊雙色有向圖指數(shù)問題的研究，已經(jīng)取得了一些重要成果[1-8]；在雙色有向圖本原指數(shù)界的基礎(chǔ)上，可以進(jìn)一步推廣研究，如含有兩個圈的雙色有向圖本原指數(shù)集[9-10]和含有三個圈的三色有向圖本原指數(shù)上界[11-13]。本文研究了如圖1所示的一類特殊雙色有向圖D，通過非負(fù)矩陣對與其伴隨有向圖的對應(yīng)關(guān)系，在文獻(xiàn)研究方法的基礎(chǔ)上，借助非負(fù)矩陣對的逆矩陣找到了任意頂點(diǎn)對(i,j)都存在從i到j(luò)的(h,k)-途徑，給出了雙色有向圖D的本原條件，找到了指數(shù)上下界，并對達(dá)到指數(shù)上下界時的極圖進(jìn)行了刻化。所得結(jié)果為非負(fù)矩陣對本原指數(shù)集、非負(fù)矩陣簇指數(shù)問題的研究奠定基礎(chǔ)。

圖1 未著色有向圖D

(1)

其中x,y都是整數(shù)。

1 本原條件

定理1 如圖1所示的雙色有向圖D是本原的，當(dāng)且僅當(dāng)x=1，y=3。

2 指數(shù)下界

則u≥2n-1。從而

3 指數(shù)上界

定理得證。

類似定理3的證明過程，可得定理4，不再贅述。

4 極圖刻化

(2)

考慮以下5種情形：

情形1：r=0時。

情形2：r=1時。

情形3：r=2時。

情形4：r=3時。

情形5：r=4時。

則u≥3a。從而

綜上所述，結(jié)合定理2，定理得證。

類似定理2和定理5的證明過程，可得定理6和定理7，不再贅述。

[ 參 考 文 獻(xiàn) ]

[1] SHADER B L,SUWILO S.Exponents of nonnegative matrix pairs[J].Linear Algebra and its Applications,2003,363:275-293.

[2] FORNASINI E,VALCHER M E.Primitivity of positive matrix pairs:algebraic characterization graph theoretic description,and 2D systems interpretation,SIAM[J].Siam Journal on Matrix Analysis & Applications,1998,19(1):71-88.

[3] WIELANDT H.Unzerlegbare,nicht negative Matrizen.Mathematische Zeitschrift,1950,52(1):642-648.

[4] DULMAGE A L,MENDELSOHN N S.Coverings of bipartite graphs.Canadian Journal of Mathematics,1958(10):517-534.

[5] 汪榮,邵燕靈,高玉斌.一類雙色有向圖本原指數(shù)的上界[J].吉林大學(xué)學(xué)報(理學(xué)版),2008,46(4):601-606.

[6] 孫濤,王建中,羅美金.一類雙色有向圖的指數(shù)上界[J].中北大學(xué)學(xué)報(自然科學(xué)版),2011,32(6):655-661.

[7] SUMARD H,SUWILO S.The scrambling index of two-colored two cycles whose lengths differ by 1[J].Far East Journal of Mathematical Science,2015,96(1):113-132.

[8] 李茜,羅美金.特殊雙色有向圖的本原指數(shù)[J].曲阜師范大學(xué)學(xué)報,2015,41(4):48-50.

[9] 李茜,羅美金.特殊雙色有向圖的本原指數(shù)的上界[J].貴州師范大學(xué)學(xué)報(自然科學(xué)版),2017,35(2):58-61.

[10] 羅美金.一類恰含一個公共點(diǎn)的雙色有向圖的本原指數(shù)集[J].暨南大學(xué)學(xué)報(自然科學(xué)版),2013,34(5):483-488.

[11] 羅美金,侯宗毅.一類特殊非負(fù)矩陣對本原指數(shù)集[J].重慶師范大學(xué)學(xué)報(自然科學(xué)版),2017,34(2):59-66.

[12] 羅美金,侯宗毅,李茜.一類恰含一個3-圈的三色本原有向圖指數(shù)上界[J].數(shù)學(xué)實(shí)踐與認(rèn)識,2017,47(20):140-146.

[13] LUO Mei-jin,LI Xi.Exponents of a class of primitive three-colored digraphs[J].Ars Combinatoria,2017,133:179-195.