一類本原有向圖的m-competition指數(shù)及廣義scrambling指數(shù)

申佳,高玉斌

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

近幾年來,對本原有向圖本原指數(shù)的研究已擴(kuò)展到對本原有向圖scramling指數(shù)和m-competition指數(shù)的研究,并取得了許多成果。2009年,Akelbek和Kirkland[1]首次提出了本原圖的scrambling指數(shù)的概念,2010年,黃宇飛等[2]以非記憶通訊系統(tǒng)為背景,對 scrambling指數(shù)進(jìn)行了推廣,引入了廣義scrambling指數(shù)的概念。2010年,Hwa Kyung Kim[3]提出了本原圖的m-competition指數(shù)這一概念。文獻(xiàn)[4-8]研究了對稱含環(huán)本原圖的m-competition指數(shù)問題。本文研究結(jié)合廣義 competition指數(shù)和廣義scrambling指數(shù)的定義,對本原圖中任一點(diǎn)經(jīng)過k長途徑所到達(dá)點(diǎn)的集合進(jìn)行分析,研究一類特殊的本原有向圖。

1 預(yù)備知識

設(shè)有向圖D,若存在一個正整數(shù)l,使得D中任意 2個頂點(diǎn) x,y(可相同),在D中都存在從x到y(tǒng)的l長途徑,則稱D是本原有向圖,其中最小的正整數(shù)l稱為D的本原指數(shù),記為exp(D)。D的本原有向圖的充分必要條件是D強(qiáng)連通,且D的所有圈長的最大公因子為1[9]。用表示從x到y(tǒng)有l(wèi)長的途徑。定義 Dl為一個本原有向圖,其中當(dāng)且僅當(dāng)D中有

定義1[2]本原有向圖D的scrambling指數(shù)是最小的正整數(shù)k,對任意一對頂點(diǎn)u和v,都存在w∈V(D),使得從u和v到w都有k長途徑,這樣的k稱為本原有向圖D的scrambling指數(shù),記為k(D)。

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

定義3[4]設(shè)D是n階本原有向圖,1≤m≤n,對于任意的頂點(diǎn) u,v ∈ V(D),存在正整數(shù)m,在D中總能找到m個點(diǎn),使得 u,v到這m個點(diǎn)都存在k長途徑(這m個點(diǎn)與u和v有關(guān)系),k的最小值稱為D的m-competition指數(shù),記作 km(D)。m-competition指數(shù)也稱為廣義competition指數(shù)。如果上述頂點(diǎn) u,v ∈ V(D)已給定,則滿足條件的最小的k稱為點(diǎn)x,y在D中的局部廣義competition指數(shù),記為

文中用文獻(xiàn)[10]中的記號 N+(Dk:x)表示在D中點(diǎn)x經(jīng)過k長途徑所到達(dá)點(diǎn)的集合,用表示集合中點(diǎn)的個數(shù)。

2 主要結(jié)論

本文研究一類含有 2個 1s-圈和s個s圈的n階本原有向圖1D和2D(圖1、圖2)的m-competition指數(shù)以及廣義scrambling指數(shù)。

圖1 1D圖

圖2 2D圖

定理 1 設(shè) n(n≥7)階本原圖 D1(D2)如圖1(圖2)所示,其中 n=2 s-1,4≤s≤n-1,則對于正整數(shù) m(1≤m≤n),有:

情形2 1≤m≤s 且s+ m 為偶數(shù)。

一方面,對任意 x,y ∈ V(D1),存在使得在D1中有且在本原有向圖(圖4)中,頂點(diǎn)均為環(huán)點(diǎn)且成一個s圈,記為2C。

圖3 圖

圖4 圖

證明 km(D1)和 km(D2)的證明過程類似,僅證明(1)式。

情形3 m≥s+2且s+m為偶數(shù)。

另一方面,取特殊點(diǎn) vn,vn-1,在圖中,易知 vn,vn-1經(jīng)過 s-1 長途徑所到達(dá)的公共點(diǎn)個數(shù)為s(＜m),所以因此,

情形4 m≥s+1且s+m為奇數(shù)。

類似地,可得到km(D2)。定理得證。

推論1 根據(jù)定理1,當(dāng)1m=時,可得本原有向圖1D和2D的scrambling指數(shù):

定理2 設(shè)n(n≥7)階本原圖D1(D2)如圖1(圖2)所示,其中

證明 僅證明(3)式。

定理3 設(shè)n(n≥7)階本原圖D1(D2)如圖1(圖2)所示,其中 n=2s-1,4≤s≤n-1,則對于正整數(shù)m(1≤m≤n),有

證明 設(shè)Cs-1是本原有向圖D1(圖1)上長為s-1圈,u1,u2,…,uλ(1≤λ≤s-1)是D1中s-1圈上的任意λ個不同的點(diǎn),則在有向圖是環(huán)點(diǎn)。于是必存在一個頂點(diǎn) w ∈ V(D)使得成立。因此,由kX(D)的定義可知,

另外,對于任意λ個頂點(diǎn)vi∈V(D1),存在頂點(diǎn)使得vi到wi有 s-1長途徑(i=1,2,…,λ)。于是當(dāng)λ≤s-1時當(dāng)λ＞s時,因此可以得到

[1]Akelbek M,Kirkland S.Coefficients of ergodicity and the scrambling index [J].Linear Algebra and its Applications,2009,430(4):1 111-1 130.

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

[3]Kim H K.Generalized competition index of a primitive digraph [J].Linear Algebra and its Applications,2010,433(1):72-79.

[4]Shao Y L,Gao Y B.The m-competition indices of symmetric primitive digraphs with loop [J].Ars Combination,2013,108:217-223.

[5]Kim H K,Pank S G.A bound of generalized competition index of a primitive digraph [J].Linear Algebra and its Applications,2012,436(1):86-98.

[6]Akelbek M,Kirkland S.Primitive digraphs with the largest scrambling index [J].Linear Algebra and its Applications,2009,430:1 099-1 110.

[7]Gao Y,Shao Y.The scrambling indices of primitive digraphs with exactly two cycles [J].Ars Combination,2013,108:505-513.

[8]Hwa K K.Scrambling index set of primitive digraphs [J].Linear Algebra and its Applications,2013,439:1 886-1 893.

[9]Brualdi R A,Ryser H J.Combinatorial Matrix Theory [M].Cambridge:Cambridge University Press,1991.

[10]Kim H K,Lee S H.Generalized competition indices of symmetric primitive digraphs [J].Discrete Applied Mathematics,2012,160(10-11):1 583-1 590.