一類雙色有向圖的本原指數(shù)的上界

李 茜，羅美金

（1.山西運城農(nóng)業(yè)職業(yè)技術(shù)學(xué)院 基礎(chǔ)部，山西 運城 044000；2.河池學(xué)院 數(shù)學(xué)與統(tǒng)計學(xué)院，廣西 宜州 546300）

一類雙色有向圖的本原指數(shù)的上界

李 茜1，羅美金2*

（1.山西運城農(nóng)業(yè)職業(yè)技術(shù)學(xué)院 基礎(chǔ)部，山西 運城 044000；2.河池學(xué)院 數(shù)學(xué)與統(tǒng)計學(xué)院，廣西 宜州 546300）

研究一類雙色有向圖，其基礎(chǔ)有向圖僅包含兩個圈，分別是n-圈與（3n-1）-圈，并給出了這個雙色有向圖的本原條件、本原指數(shù)上界，以及對達到上界的極圖進行了刻畫.

雙色有向圖；本原指數(shù)；極圖

一個雙色有向圖是指其弧被著色為紅色、藍色的有向圖.若對D的任一對頂點（i，j），都有從i到j(luò)的途徑，則稱雙色有向圖D是強連通的.對于雙色有向圖D的一條途徑w，用r（w），b（w）分別表示w的紅弧、藍弧的個數(shù)，則w分解為向量（r（w），b（w））或（r（w），b（w））T.若w的分解為（h，k），則稱w為一條（h，k）-途徑.

雙色有向圖D是本原的，若存在非負整數(shù)h和k且h+k>0，使得對于D中的每對頂點（i，j），都有從i到j(luò)的（h，k）-途徑.并將h+k的最小值稱為雙色有向圖D的本原指數(shù)，記為exp（D）.

設(shè)C={r1，r2，…，rl}是D的圈的集合，M為2×l矩陣，其第i列是ri的分解，則稱M為D的圈矩陣.將M的content（記為content（M））定義為0，若M的秩小于2，否則，定義為M的所有非零二階主子式的最大公因子.

目前，關(guān)于雙色有向圖的本原指數(shù)的研究已經(jīng)取得了一些成果，參見文獻[1-8].本文研究一類雙圈雙色有向圖D，其基礎(chǔ)有向圖見圖1.

圖1 基礎(chǔ)有向圖Fig.1Uncolored digraph D

1 本原條件

引理1[1]一個至少包含一條紅弧和一條藍弧的雙色有向圖D是本原的，當且僅當D是強連通的，且content（M）=1.

定理1 雙色有向圖D是本原的，當且僅當

a（3n-1）-bn=±1，且

（1）當a（3n-1）-bn=1時，a=n-1，b=3n-4.

（2）當a（3n-1）-bn=-1時，a=1，b=3.

證明 顯然D是強連通的，det（M）=a（3n-1）-bn.由引理1，D是本原的當且僅當det（M）=±1，即a（3n-1）-bn=±1.容易驗證，當a（3n-1）-bn=1時，a=n-1，b= 3n-4；當a（3n-1）-bn=-1時，a=1，b=3.證畢.

2 本原指數(shù)的上界

定理2 若雙色有向圖D是本原的，且a（3n-1）-bn=1，則exp（D）≤24n2-31n+4.

證明 由定理1，D的圈矩陣為

對于D的每對頂點（i，j），用Pij表示從i到j(luò)的最短路，s=r（Pij），t=b（Pij）.

只需證明對于D的每對頂點（i，j），都有一條（24n2-55n+31，24n-27）-途徑.取

因此，從頂點i出發(fā)，沿Pij到頂點j，轉(zhuǎn)n-圈ρ1次，轉(zhuǎn)（3n-1）-圈ρ2次，其途徑可分解為

顯然，s≤4n-5，t≤4，且ρ1≥0，ρ2≥0.當s=4n-5時，t≥0.當t=4時，s≥0.此時必包含公共頂點n.

所以exp（D）≤24n2-55n+31+24n-27=24n2-31n+ 4.證畢.

定理3 若雙色有向圖D本原，且a（3n-1）-bn= -1，則exp（D）≤24n2-31n+4.

證明 類似于定理2可證.

3 指數(shù)上界的極圖刻畫

定理4 若雙色有向圖D是本原的，且a（3n-1）-bn=1，則exp（D）=24n2-31n+4，當且僅當D中存在4n-5長的連續(xù)紅路.

證明 充分性：由定理2，只需證明exp（D）≥24n2-31n+4.

所以，v≥4n-4.

則

結(jié)合定理2，可得exp（D）=24n2-31n+4.

必要性：反證法.假設(shè)D中不存在4n-5長的連續(xù)紅路，因為D是本原的，且a（3n-1）-bn=1，所以只需證明exp（D）<24n2-31n+4.

對于D的每對頂點（i，j），用Pij表示從i到j(luò)的最短路，s=r（Pij），t=b（Pij）.

只需證明對于D的每對頂點（i，j）都有一條（24n2-61n+38，24n-33）-途徑.取

ρ1=12n-18-3s+（3n-4）t，ρ2=4n-5-（n-1）t+s，因此，從頂點i出發(fā)，沿Pij到頂點j，轉(zhuǎn)n-圈ρ1次，轉(zhuǎn)（3n-1）-圈ρ2次的途徑可分解為

顯然，s≤4n-5，t≤4.

（1）當t=0時，0≤s≤4n-6.且ρ1≥0，ρ2>0.

（2）當t=1時，0≤s≤4n-5.且ρ1>0，ρ2>0.

（3）當t=2時，0≤s≤4n-5.且ρ1>0，ρ2>0.

（4）當t=3時，0≤s≤4n-6.且ρ1>0，ρ2>0.

（5）當t=4時，1≤s≤4n-7.且ρ1>0，ρ2≥0.

所以，

證畢.

定理5 若雙色有向圖D本原，且a（3n-1）-bn= -1，則exp（D）=24n2-31n+4，當且僅當D中存在4n-5長的連續(xù)藍路.

證明 類似于定理4可證.

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

[2]Shao Yanling,Gao Yubin,Sun Liang.Exponents of a class of two-colored digraphs[J].Linear and Multilinear Algrbra, 2005,53(3):175-188.

[3]Gao Yubin,Shao Yanling.Exponents of two-colored di?graphs with two cycles[J].Linear Algebra and Its Applica?tions,2005,407:263-276.

[4]Gao Yubin,Shao Yanling.Generalized exponents of primi?tive two-colored digraphs[J].Linear Algebra and Its Appli?cations,2008,430(5):1550-1565.

[5]Shao Yanling,Gao Yubin,Sun Liang.On the exponents of two-colored digraphs with two cycles[J].Linear and Multi?linear Algebra,2009,57(2):185-199.

[6]羅美金.一類雙色有向圖的本原指數(shù)集[J].數(shù)學(xué)的實踐與認識,2012,42(24):253-258.

[7]羅美金.一類雙色有向圖的本原指數(shù)上界[J].數(shù)學(xué)的實踐與認識,2013,43(23):142-150.

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

責(zé)任編輯：畢和平

Upper Bound on Primitive Exponent of a Class of Two-colored Digraphs

LI Xi1，LUO Meijin2＊
（1.Department of Basic Education，Yuncheng Vocational College of Agriculture，Yuncheng044000，China；2.School of Mathematics and Statistics，Hechi University，Yizhou546300，China）

A class of two-colored digraphs whose uncolored digraph consists of onen-cycle and one（3n-1）-cycle.Some primitive conditions,an upper bound on the exponent,and the characterizations of the extremal two-colored digraphs.

two-colored digraph；primitive exponent；extremal digraph

O 157.5

：A

：1674-4942（2015）01-0020-02

2014-10-29

廣西自治區(qū)高等學(xué)?？蒲许椖浚╕B2014335）

*通訊作者