本原有向圖的scrambling指數(shù)和m-competition指數(shù)

方 煒，高玉斌

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

0 引 言

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

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

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

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

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

1 主要結(jié)論

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

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

圖1 D1 Fig.1 D1

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

圖2 Dn1-2 Fig.2 Dn1-2

1）當(dāng)n≡0（mod 4）時(shí)，在Dn-21中

因此在Dn-21中同時(shí) 對(duì)于頂點(diǎn)有同時(shí)在本原有向圖D1中，對(duì)于任意的頂點(diǎn)vi，vj∈V（D1），vi，vj經(jīng)過(guò)1長(zhǎng)途徑都至少能到達(dá)頂點(diǎn)集合｛v1，v2，…，vn-2｝中 的 一 個(gè) 點(diǎn)，所 以

情況1 1≤i，j≤n-1.因?yàn)閨V1|=n-2，所以對(duì)于任意的頂點(diǎn)

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

4）當(dāng)n≡3（mod 4）時(shí)，

在D1中，當(dāng)時(shí)，且同 時(shí)，其中有個(gè)點(diǎn)屬于V2.

定理2 設(shè)D2為n階有向圖，如圖3所示，D2含有1個(gè)n-3長(zhǎng)圈和1個(gè)n-4長(zhǎng)圈.

圖3 D2 Fig.3 D 2

證明 令vi，vj∈V（D2），如果在本原有向圖D2中，vi經(jīng)過(guò)n-4長(zhǎng)途徑能到達(dá)vj，那么在本原有向圖Dn-41中，vi經(jīng)過(guò)1長(zhǎng)途徑能到達(dá)vj.如果在本原有向圖D2中，vi經(jīng)過(guò)n-3長(zhǎng)途徑能到達(dá)vj，那么在本原有向圖Dn-31中，vi經(jīng)過(guò)1長(zhǎng)途徑能到達(dá)vj.

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

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

圖4 Dn-42 Fig.4 Dn-42

圖5 Dn-32 Fig.5 Dn-32

1）當(dāng)n+m為奇數(shù)時(shí)，在Dn-42中，令因?yàn)槭?環(huán) 點(diǎn)，所 以其中在D2中，點(diǎn)集中的任意一個(gè)頂點(diǎn)經(jīng)過(guò)4長(zhǎng)途徑都能到達(dá)而且

在本原有向圖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.