一個(gè)特殊本原有向圖的廣義competition及scrambling指數(shù)

張佩,高玉斌

(中北大學(xué) 數(shù)學(xué)系,山西 太原,030051)

1 相關(guān)知識(shí)與理論

設(shè)D是一個(gè)有向圖(允許有環(huán)但不能有重復(fù)弧),D的一條長(zhǎng)為l的途徑是指連續(xù)的頂點(diǎn)序列 v1,v2,…,vl+1,對(duì)所有的 i=1,2,…,l,D中都有從 vi到 vi+1的弧。用記號(hào)表示從vi到vj的l長(zhǎng)途徑。另外,Dl是一個(gè)有向圖,其中當(dāng)且僅當(dāng)在有向圖D中

定義1[1]設(shè)有向圖D,若存在1個(gè)正整數(shù)l,使得D中的任意2個(gè)頂點(diǎn) x,y(可以相同),在D中都存在從x到y(tǒng)的l長(zhǎng)途徑,則稱D是本原有向圖,其中最小的正整數(shù)l稱為本原指數(shù),記為exp(D)。

引理1[1]有向圖D是本原的充分必要條件是D為強(qiáng)連通,且D的所有圈長(zhǎng)的最大公因子為1。

定義 2[2–3]設(shè)D是n階本原有向圖,如果存在正整數(shù)k,對(duì)D中任意頂點(diǎn)u和v,都存在頂點(diǎn)w∈V(D),使得從u和v到w都有k長(zhǎng)途徑,滿足上述條件的最小正整數(shù)k,稱為本原有向圖D的scrambling指數(shù),記為k(D)。

定義3[4]設(shè)D是n階本原有向圖,小的正整數(shù)l,使得存在μ個(gè)頂點(diǎn)w1,w2,…,wμ∈V(D),對(duì)于任意x∈X,從x到wi(i=1,2,…,μ)都有l(wèi)長(zhǎng)小途徑,則分別稱為本原有向圖D的λ重下μ-s crambling 指數(shù)和λ重上 μ-scrambling 指數(shù)。特別地,當(dāng)μ=1時(shí),稱 h(D,λ)和 k(D,λ)為有向圖D的廣義scramb-ling指數(shù)。

引理2[4]定義4[5]設(shè)D是n階本原有向圖及m為正整數(shù),1≤m≤n。若存在正整數(shù)k,對(duì)任意2個(gè)頂點(diǎn)0,x能找到m個(gè)不同的頂點(diǎn)vi∈V(D)(i=1,2,…,m)使得在D中有則稱滿足上述條件的k為D的 m-c ompetition 指數(shù),記為

引理3[5]當(dāng)m=1時(shí),k1(D)=k(D); 當(dāng)m=n 時(shí),

定義5[5]設(shè)D是n階本原有向圖,及頂點(diǎn) x0,y0∈ V(D)與正整數(shù)若存在正整數(shù)k,能找到m個(gè)不同的頂點(diǎn)使得在D中有則稱滿足上述條件的k為點(diǎn) x0,y0在D中的局部 m-c ompetition 指數(shù),記為由此,可以得到

另外,本文用文獻(xiàn)[6]中的記號(hào) N+(Dk:x)表示點(diǎn)x在D中經(jīng)過k長(zhǎng)途徑所能到達(dá)點(diǎn)的集合,即點(diǎn)x在中經(jīng)過1長(zhǎng)途徑所能到達(dá)點(diǎn)的集合,而表示集合中頂點(diǎn)的個(gè)數(shù)。

2 主要結(jié)論

定理1 設(shè)D為如圖1所示的 8n≥階本原有向圖,則有

證明 本原有向圖D中含有1個(gè) 3n-圈,2個(gè) 4n-圈。

情形1 n+ m 為奇數(shù)且 m≤n-5。

圖1 本原有向圖D

情形3 m=n-3。

定理1得證。

定理2 設(shè)D是n階本原有向圖,如圖1所示,則

由上可知,存在頂點(diǎn) v2∈ V(DT),使得因此,存在一個(gè)頂點(diǎn) v ∈ V(DT),使得

綜上所述,h(D, λ) = t。定理2得證。

定理3 設(shè)D是n階本原有向圖,如圖1所示,則有:

證明 設(shè) u1,u2,…,um(1≤m≤n-4)是本原有向圖D(圖1)中 n-4 圈上的任意m個(gè)互異的點(diǎn)。首先證明考慮有向圖 D(n-4),顯然 u1,u2,…,um是有向圖D(n-4)上的環(huán)點(diǎn),故1)-n(m-1)≥1 。因此,在D(n-4)中存在一個(gè)頂點(diǎn) w ∈ V(D(n-4))使得或者說D中存在一個(gè)頂點(diǎn) w ∈ V(D)使得。因此,由 kX(D)的定義可知,

[1]Brualdi R A,Ryse H J.Combinatorial Matrix Theory [M].New York:Cambridge University Press,1991.

[2]Akelbek M,Kirkland S.Coefficients of ergodicity and scrambling index [J].Linear Algebra and Its Applications,2009,430:1 111–1 130.

[3]Liu B,Huang Y.The scrambling index of primitive digraphs [J].Computers and Mathematics with Applications,2010,60:706–721.

[4]Huang Y,Liu B.Generalized scrambling indices of a primitive digraphs [J].Linear Algebra and Its Applications,2010,433:1 798–1 808.

[5]Kim H K.Generalized competiton index of a primtitive digraph [J].Linear Algebra and Its Applications,2010,433:72–79.

[6]Kim H K,Pank S G.A bound of generalized competiton index of a primtitive digraph [J].Linear Algebra and Its Applications,2012,436:86–98.