李 茜，羅美金

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

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

李 茜1，羅美金2*

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

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

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

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

雙色有向圖D是本原的，若存在非負(fù)整數(shù)h和k且h+k>0，使得對(duì)于D中的每對(duì)頂點(diǎn)（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)取得了一些成果，參見(jiàn)文獻(xiàn)[1-8].本文研究一類雙圈雙色有向圖D，其基礎(chǔ)有向圖見(jiàn)圖1.

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

1 本原條件

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

定理1 雙色有向圖D是本原的，當(dāng)且僅當(dāng)

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

（1）當(dāng)a（3n-1）-bn=1時(shí)，a=n-1，b=3n-4.

（2）當(dāng)a（3n-1）-bn=-1時(shí)，a=1，b=3.

證明 顯然D是強(qiáng)連通的，det（M）=a（3n-1）-bn.由引理1，D是本原的當(dāng)且僅當(dāng)det（M）=±1，即a（3n-1）-bn=±1.容易驗(yàn)證，當(dāng)a（3n-1）-bn=1時(shí)，a=n-1，b= 3n-4；當(dāng)a（3n-1）-bn=-1時(shí)，a=1，b=3.證畢.

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

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

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

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

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

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

顯然，s≤4n-5，t≤4，且ρ1≥0，ρ2≥0.當(dāng)s=4n-5時(shí)，t≥0.當(dāng)t=4時(shí)，s≥0.此時(shí)必包含公共頂點(diǎn)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ù)上界的極圖刻畫(huà)

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

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

所以，v≥4n-4.

則

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

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

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

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

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

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

（1）當(dāng)t=0時(shí)，0≤s≤4n-6.且ρ1≥0，ρ2>0.

（2）當(dāng)t=1時(shí)，0≤s≤4n-5.且ρ1>0，ρ2>0.

（3）當(dāng)t=2時(shí)，0≤s≤4n-5.且ρ1>0，ρ2>0.

（4）當(dāng)t=3時(shí)，0≤s≤4n-6.且ρ1>0，ρ2>0.

（5）當(dāng)t=4時(shí)，1≤s≤4n-7.且ρ1>0，ρ2≥0.

所以，

證畢.

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

證明 類似于定理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é)的實(shí)踐與認(rèn)識(shí),2012,42(24):253-258.

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

[8]羅美金.一類恰含一個(gè)公共點(diǎn)的雙色有向圖的本原指數(shù)集[J].暨南大學(xué)學(xué)報(bào):自然科學(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é)?？蒲许?xiàng)目（YB2014335）

*通訊作者