方 煒，高玉斌

（1.中北大學 儀器與電子學院，山西 太原030051；2.中北大學 理學院，山西 太原030051）

0 引 言

令D=（V，E）是一個有向圖，其點集V=V（D），邊集E=E（D）.可以有環(huán)但是不能有重弧.用Cp來表示一個長度為p的圈.一個有向圖D是本原的，當且僅當存在正整數(shù)k，使得D中的任意一點x到另外一點y（y可能等于x）都存在k長途徑.這樣的最小的正整數(shù)k就是有向圖D的本原指數(shù)，用exp（D）表示.

在2009年，Akelbek和Kirkland［1］共同提出了本原有向圖scrambling的指數(shù)這一概念.在本原有向圖D中，如果對于任意一對頂點u，v，都能在D中找到一個頂點w并且u，v經過k長途徑都能到達w，滿足這樣條件的最小的正整數(shù)k就稱為本原有向圖D的scrambling指數(shù)，用k（D）表示.

在2010年，Hwa Kyung Kim［2］提出了本原有向圖m-competition指數(shù)的概念，在本原有向圖D中，如果對于任意一對頂點u，v，都能在D中找到一個頂點集合V1=u1，v2，…，um-1，um，|V1|=m，并且u，v經過k長途徑都能到達頂點集合V1，滿足這樣條件的最小的正整數(shù)k就稱為D的mcompetition指數(shù)，用km（D）表示.其實m-competition指數(shù)是一種廣義的scrambling指數(shù).

對于n階本原有向圖D，通過本原指數(shù)，scrambling指數(shù)和m-competition指數(shù)的概念，可以這樣的關系：k（D）=k1（D）≤k2（D）≤…≤kn（D）=exp（D）.

近年來，國內外很多專家對本原有向圖的scrambling指數(shù)和m-competition指數(shù)進行了研究，如文獻［3-15］.在文獻［3］中，作者找到了本原有向圖scrambling指數(shù)的上界，并找了取得上界的極圖；在文獻［4］中，作者研究了對稱本原有向圖的scrambling指數(shù)；在文獻［5］中，作者研究了僅含兩個圈的本原有向圖scrambling指數(shù)；在文獻［6］中，作者研究了本原對稱含環(huán)有向圖的m-competition指數(shù).本文研究了一類含三個圈的本原有向圖的srambling指數(shù)和一類僅含兩個圈的本原有向圖的m-competition指數(shù).

1 主要結論

為了表達方便，用|Rt｛x｝|表示頂點x在D中經過t長途徑所到達的頂點個數(shù).令點集V1?V，用RV1t｛x｝表示頂點x經過t長途徑到達V1中的點集，即RV1t｛x｝=Rt｛x｝∩V1.設D為n階本原有向圖，vi，vj∈V（D），如果在D中，vi經過t（t為正整數(shù)）長途徑能到達vj，那么在有向圖Dt中，vi只需經過1長途徑就能到達vj.

定理1 設D1為如圖1所示的n階本原有向圖，

圖1 D1 Fig.1 D1

證明 令vi，vj∈V（D1），如果在本原有向圖D1中，vi經過n-2長途徑能到達vj，那么在本原有向圖Dn-21中，vi經過1長途徑能到達vj.由本原有向圖D1，可以得到Dn-21，如圖2所示：

圖2 Dn1-2 Fig.2 Dn1-2

1）當n≡0（mod 4）時，在Dn-21中

因此在Dn-21中同時 對于頂點有同時在本原有向圖D1中，對于任意的頂點vi，vj∈V（D1），vi，vj經過1長途徑都至少能到達頂點集合｛v1，v2，…，vn-2｝中 的 一 個 點，所 以

情況1 1≤i，j≤n-1.因為|V1|=n-2，所以對于任意的頂點

情況2 1≤i≤n-1，j=n.

4）當n≡3（mod 4）時，

在D1中，當時，且同 時，其中有個點屬于V2.

定理2 設D2為n階有向圖，如圖3所示，D2含有1個n-3長圈和1個n-4長圈.

圖3 D2 Fig.3 D 2

證明 令vi，vj∈V（D2），如果在本原有向圖D2中，vi經過n-4長途徑能到達vj，那么在本原有向圖Dn-41中，vi經過1長途徑能到達vj.如果在本原有向圖D2中，vi經過n-3長途徑能到達vj，那么在本原有向圖Dn-31中，vi經過1長途徑能到達vj.

由本原有向圖D2，可以得到Dn-42，如圖4所示：

也可以得到Dn-32，如圖5所示：

圖4 Dn-42 Fig.4 Dn-42

圖5 Dn-32 Fig.5 Dn-32

1）當n+m為奇數(shù)時，在Dn-42中，令因為是 環(huán) 點，所 以其中在D2中，點集中的任意一個頂點經過4長途徑都能到達而且

在本原有向圖D2中，

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

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

［3］Akelbek M，Kirkland S.Primitive digraphs with the largest scrambling index［J］.Linear Algebra Appl.，2009，430（4）：1099-1110.

［4］Chen Shexi，Liu Bolian.The scrambling index of symmetric primitive matrices［J］.Linear Algebra and its Applications，2010，433（6）：1110-1126.

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

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

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

［8］Liu Bolian，Huang Yufei.The scrambling index of primitive digraphs［J］.Computers and Mathematics with Applications，2010，60（3）：706-721.

［9］Cho H H，Kim S R，Nam Y S.The m-step competition graph of a digraph［J］.Discrete Applied Mathematics，2010，105（1-3）：115-127.

［10］Kim H K.A bound on the generalized competition index of a primitive matrix using boolean rank［J］.Linear Algebra and Its Application，2011，435（9）：2166-2174.

［11］Kim H K，Park S G.Generalized competition indices of symmetric primitive digraphs［J］.Linear Algebra and Its Application，2012，436（1）：86-98.

［12］Kim H K.Generalized competition index of an irreducible boolean matrix［J］.Linear Algebra and Its Application，2013，438（6）：2747-2756.

［13］Kim H K.Scrambling index set of primitive digraphs［J］.Linear Algebra and Its Application，2013，439（7）：1886-1893.

［14］Shao Yanling，Gao Yubin，Li Zhongshan.The mcompetition indices of symmetric primitive digraphs without loops［J］.Electronic Journal of Linear Algebra，2012，23：457-472.

［15］Shao Yanling，Gao Yubin，Li Zhongshan.On the second largest scrambling index of primitive matrices［J］.Ars Combination，2014，113：457-462.