宋卓蓉，高玉斌

（中北大學(xué) 理學(xué)院，山西 太原030051）

1 預(yù)備知識(shí)

本原有向圖本原指數(shù)［1］的研究已經(jīng)逐步擴(kuò)展到了對(duì)本原有向圖的scrambling指數(shù)［2-3］的研究.本原有向圖的scrambling指數(shù)是一個(gè)新興研究分支，也是近兩年來在組合數(shù)學(xué)中較為活躍的一個(gè)研究方向，在計(jì)算機(jī)科學(xué)中具有廣泛的實(shí)際應(yīng)用背景.近年，許多學(xué)者又將scrambling指數(shù)推廣到m-competition指數(shù)［4-8］，進(jìn)行了廣泛的研究.

設(shè)D=（V，E）是一個(gè)n階有向圖，其中頂點(diǎn)集V=V（D），弧集E=E（D）（允許有環(huán)但無重弧）.一個(gè)有向圖D是本原的，當(dāng)且僅當(dāng)存在正整數(shù)k，使得D中的任意一點(diǎn)x到另外一點(diǎn)y（y可能等于x）都存在k長途徑.稱滿足上述條件的最小正整數(shù)k為有向圖D的本原指數(shù)，記為exp（D）.

設(shè)D是一個(gè)n階本原有向圖，k∈Z+，對(duì)于任意頂點(diǎn)x，y∈V（D），用N+（Dk∶x）=｛v∈V（D）|x →kv｝表示頂點(diǎn)x經(jīng)過k長途徑所到達(dá)的點(diǎn)的集合，用|N+（Dk∶x）|表示此集合中點(diǎn)的個(gè)數(shù).用N+（Dk∶x，y）=N+（Dk∶x）∩N+（Dk∶y）表示頂點(diǎn)x，y經(jīng)過k長途徑所到達(dá)的公共點(diǎn)的集合，用|N+（Dk∶x，y）|表示此集合中點(diǎn)的個(gè)數(shù).

如果D為一個(gè)n階本原有向圖，k為正整數(shù)，則Dk也是本原有向圖，其中V（Dk）=V（D），E（Dk）=｛vi，vj）|在D中有vi→kvj｝.

定義1［4］設(shè)D是n階本原有向圖，如果存在正整數(shù)k，對(duì)于D中任意頂點(diǎn)x和y，都存在m（1≤m≤n）個(gè)不同的頂點(diǎn)v1，v2，…，vm∈V（D）使得x →kvi，y →kvi，（1≤i≤m），滿足上述條件的最小正整數(shù)k稱為本原有向圖D的m-competition指數(shù)，記為km（D）.特殊地，k（D）=k1（D），exp（D）=kn（D）.

定義2［4］設(shè)D是n階本原有向圖，如果存在正整數(shù)k，對(duì)D中兩個(gè)不同的頂點(diǎn)x和y，都存在m（1≤m≤n）個(gè)不同的頂點(diǎn)v1，v2，…，vm∈V（D）使得x →kvi，y →kvi，（1≤i≤m），滿足上述條件的最小正整數(shù)k稱為頂點(diǎn)x和y的局部m-competition指數(shù)，記為km（D∶x，y）.

2 主要結(jié)論及證明

設(shè)n≥7，gcd（n，3）=1，D是恰含一個(gè)n圈和兩個(gè)n-3圈的n階本原有向圖.容易得出，在同構(gòu)意義下，這樣的本原有向圖D共有三種形式D1，D2和D3（如圖1～圖3所示）.下文將分別給出這三個(gè)本原有向圖的m-competition指數(shù).在證明過程中，頂點(diǎn)的指標(biāo)按mod n來對(duì)待.如vn+1=v1，vn+2=v2，v0=vn，v-1=vn-1，v-2=vn-2等.

圖1 有向圖D 1 Fig.1 Digraph D 1

圖2 有向圖D 2 Fig.2 Digraph D 2

圖3 有向圖D 3 Fig.3 Digraph D3

定理1 設(shè)D1是如圖1所示的n階本原有向圖，其中n≥7，gcg（n，3）=1，則對(duì)任意1≤m≤n，有

證明 因?yàn)間cd（n，3）=1，不妨設(shè)n=3k+1，n=3k+2（k∈Z+）.

情形1 n=3k+1.

情形1.1 n+m為偶數(shù).

觀察圖1中D1，頂點(diǎn)v2，v3，…，vn-2構(gòu)成一個(gè)n-3圈，不妨將這個(gè)n-3圈記為C1.在圖D1中，任取u，v∈V（D1），總存在C1中的點(diǎn)vi，vj（i，j=2，…，n-2），使得u →2vi，v →2vj.所以只需證明對(duì)任意i，j=2，…，n-2，均有

觀察圖4中Dn-31可知，v2，v3，…，vn-2點(diǎn)均為環(huán)點(diǎn).對(duì)任意vi，vj∈V（C1）（i，j=2，…，n-2），

圖4 有向圖Dn1-3 Fig.4 Digraph Dn1-3

在圖D1中，頂點(diǎn)v2，v3，…，vn-2構(gòu)成一個(gè)n-3圈，已記為C1，任取u，v∈V（D1），總存在C1中的點(diǎn)vi，vj（i，j=2，…，n-2），使得u →2 vi，v →2vj.所以只需證明對(duì)任意i，j=2，…，n-2，均有

在圖5的Dn1中

圖5 有向圖Dn1 Fig.5 Digraph Dn1

在圖Dn1中，令M1為Dn1的一個(gè)導(dǎo)出子圖.

則對(duì)任意u，v∈V（D1），均有故km（D1：由u，v的任意性，

情形2 n=3k+2.

此時(shí)本原有向圖Dn-31，Dn1與情況1中的本原有向圖Dn-31，Dn1的不同之處在于點(diǎn)的排列順序不同，故它們是同構(gòu)的，所以在這種情形下，結(jié)論亦成立.

定理得證.

定理2 設(shè)D2是如圖2所示的n階本原有向圖，其中n≥7，gcd（n，3）=1，則對(duì)任意1≤m≤n，有

圖6 有向圖Dn-32 Fig.6 Digraph Dn-32

證明 因?yàn)間cd（n，3）=1，不妨設(shè)n=3k+1，n=3k+2（k∈Z+）.

情形1 n=3k+1.

情形1.1 n+m為偶數(shù).

1）n與m均為偶數(shù).

2）n與m均為奇數(shù).

圖7 有向圖Dn2 Fig.7 Digraph Dn2

在圖D2中，頂點(diǎn)v1，v2，…，vn-3形成一個(gè)n-3圈，已記為C2.

在圖7的Dn2圖中，令M2為Dn2的一個(gè)導(dǎo)出子圖

所 以，任 取u，v∈V（D2），均 有由u，v的任意性，可知

情形2 n=3k+2.

此時(shí)本原有向圖Dn-32，Dn2與情況1中的本原有向圖Dn-32，Dn2的不同之處在于點(diǎn)的排列順序不同，故它們是同構(gòu)的，所以在這種情形下，結(jié)論亦成立.

定理得證.

定理3 設(shè)D3是如圖3所示的n階本原有向圖，其中n≥7，gcd（n，3）=1，則對(duì)任意1≤m≤n，有

［1］Brualdi R A，Ryser H J.Combinatorial Matrix Theory［M］.London：Cambridge University Press，1991.

［2］Akelbek M，Kirkland S.Coefficients of ergodicity and the scrambling index［J］.Linear Algebra and its Applications，2009（430）：1111-1130.

［3］Huang Y，Liu B.Generalized scrambling indices of a primitive digraphs［J］.Linear Algebra and its Applications，2010（433）：1798-1808.

［4］Kim H K.Generalized competition index of a primitive digraph［J］.Linear Algebra and its Applications，2010（433）：72-79.

［5］Gao Y，Shao Y.The scrambling indices of primitive digraphs with exactly two cycles［J］.Ars Combination，2013（108）：505-513.

［6］Shao Y，Gao Y.The m-competition indices of symmetric primitive digraphs with loop［J］.Ars Combination，2013（108）：217-223.

［7］Kim H K，Pank S G.A bound of generalized competition index of a primitive digraph［J］.Linear Algebra and its Applications，2012（436）：86-98.

［8］Kim H K，Lee S H.Generalized competition indices of symmetric primitive digraphs［J］.Discrete Applied Mathematics，2012（160）：1583-1590.