兩類n階本原有向圖的廣義competition指數(shù)

郝慧娥，高玉斌

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

0 引言

近年來，基于非記憶通訊系統(tǒng)中信息傳遞的研究，M．Akelbek、柳伯濂等引入了scrambling指數(shù)及其廣義scrambling指數(shù)．在文獻(xiàn)［1］［2］中作者給出scrambling指數(shù)和廣義scrambling指數(shù)的定義，文獻(xiàn)［3］中，作者刻劃了具有最大scrambling指數(shù)的本原有向圖，文獻(xiàn)［4］中，Hwa Kyung K im和Sung Gi P ark引入本原有向圖的廣義competition指數(shù)的定義，文獻(xiàn)［4－8］得到了一些本原有向圖的廣義competition指數(shù)，并進(jìn)行了極圖刻畫．本文將研究?jī)深恘階本原有向圖的廣義competition指數(shù)．文章中所涉及到的符號(hào)表示的含義詳見文獻(xiàn)［4］［7］［8］．

定義1 設(shè)D是n階本原有向圖．如果存在正整數(shù)k，對(duì)D中任意頂點(diǎn)vi和vj，總存在w∈V(D)，這里w可能與vi，vj有關(guān)，使得從vi和vj到w都有k長(zhǎng)途徑，滿足這樣條件的最小正整數(shù)k稱為n階本原有向圖D的scrambling指數(shù)，記作k(D)．

定義2 設(shè)D為n階本原有向圖，1≤m≤n，對(duì)于任意的頂點(diǎn)u，v∈V(D)，存在正整數(shù)m，在D中總能找到m個(gè)點(diǎn)，使得u，v到這m個(gè)點(diǎn)都存在k長(zhǎng)途徑，上述k的最小值稱為D的m－competiiton指數(shù)，記作km(D)．m－competiiton．指數(shù)也稱為廣義competition指數(shù)．

定義3 設(shè)D是本原有向圖，v∈V(D)，則RDt(v)表示有向圖D中頂點(diǎn)v經(jīng)過t長(zhǎng)途徑所能到達(dá)的頂點(diǎn)的集合，其中t為非負(fù)整數(shù)．

1 主要結(jié)論

定理 1 設(shè) D1為 n(≥3)階本原有向圖，其頂點(diǎn)集 V(D1)={v1，v2，…，vn－1，vn}，邊集 E(D1)={(vi，vi+1)|i=1，2，…，n － 1}∪{(vn－1，v1)，(vn－1，v2)，(vn，v2)}，則本原有向圖 D1的廣義 competition 指數(shù) km

證明:設(shè) C 是 n－2長(zhǎng)圈，x，y∈V(D1)．由 D1的本原性可得是本原的，V)=V(D1)，E()={(vi，vi－1)|i=2，…，n}∪{(vi，vi)|i=2，3，…，n －1}∪{(v1，vn－1)，(v2，vn)}

Case 1 n+m 是偶數(shù)．

由本原有向圖 D1可得V(C)，使得(x，vi)，(y，vj)∈E(D1)．在本原有向圖中都是環(huán)點(diǎn)，從經(jīng)過長(zhǎng)途徑所能到達(dá)的點(diǎn)的個(gè)數(shù)最少為同理．若從v，v至少有一個(gè)點(diǎn)經(jīng)過ij長(zhǎng)途徑所能到達(dá)的點(diǎn)中包含v1，不妨設(shè)vi，則，故反之，則故從 vi，vj經(jīng)過長(zhǎng)途徑所能到達(dá)的公共點(diǎn)的個(gè)數(shù)最小為m．因此，從而另一方面，對(duì)于長(zhǎng)途徑所能到達(dá)的公共點(diǎn)的個(gè)數(shù)小于m ，所以

Case 2 n+m是奇數(shù)．(1≤m≤n－1)

同理本原有向圖 D1中∈V(C)，使得都是環(huán)點(diǎn)，從vi經(jīng)過長(zhǎng)途徑所能到達(dá)的點(diǎn)的個(gè)數(shù)最少為同理．除環(huán)點(diǎn)外有且僅有兩個(gè)n－1圈，故從經(jīng)過長(zhǎng)途徑所能到達(dá)的公共點(diǎn)的個(gè)數(shù)最小為m．因此

定理得證．

定理 2 設(shè) D2為 n(≥3)階本原有向圖，其頂點(diǎn)集，則本原有向圖 D2的廣義 competition 指數(shù)

證明:設(shè) C1是 n－3長(zhǎng)圈，C2是 n－2長(zhǎng)圈．x，y∈V(D2)．

Case 1 n+m是偶數(shù)．

由本原有向圖 D2可得∈V(C1)，使得(x，vi)，(y，vj)∈E(D2)．:

vi， vj都是環(huán)點(diǎn)，從 vi經(jīng)過長(zhǎng)途徑所能到達(dá)的點(diǎn)的個(gè)數(shù)最少為同理，故從 v，v經(jīng)過ij長(zhǎng)途徑所能到達(dá)的公共點(diǎn)的個(gè)數(shù)最小為m．因此，km(:vi，vj)≤，

從而km(D2:x，y)≤1+()(n－3)

另一方面，對(duì)于 v1，v[]∈V()，v1經(jīng)過長(zhǎng)途徑所能到達(dá)的點(diǎn)集 {vn，vn－2，vn－3，…，}，經(jīng)過長(zhǎng)途徑所能到達(dá)的點(diǎn)集 {，…，vn，v2，vn－1，v1，vn，vn－2，vn－3，…，}，從經(jīng)過長(zhǎng)途徑所能到達(dá)的公共點(diǎn)的個(gè)數(shù)小于m，所以k(D:v，v)＞ ()(n－3)．m2ij

Case 2 n+m是奇數(shù)．

vi，vj都是環(huán)點(diǎn)，從 vi經(jīng)過長(zhǎng)途徑所能到達(dá)的點(diǎn)的個(gè)數(shù)最少為同理包含一個(gè)n－3長(zhǎng)圈，故從 vi，vj經(jīng)過長(zhǎng)途徑所能到達(dá)的公共點(diǎn)的個(gè)數(shù)最小為 m．因此，km(:vi，vj)≤，從而k(D:x，y)≤1+()(n－2)m2

［1］ Mahmud Akelbek，Steve Kirkland ．Coefficients of ergodicity and the scrambling index［J］．Linear Algebra and its Applications，2009，430:1111 －1130．

［2］ Yufei Huang，Bolian Liu．Generalized scrambling indices of a primitive digraph［J］．Linear Algebra and its Applications，2010，433:1798－1808．

［3］ Mahmud Akelbek，Steve Kirkland ．Primitive digraphs with the largest scrambling index［J］．Linear Algebra and its Applications，2009，430:1109 －1110．

［4］ Hwa Kyung Kim．Generalized competition index of a primitive digraph［J］．Linear Algebra and its Applications，2010，433:72 －79．

［5］ Hwa Kyung Kim，Sung Gi Park．A bound of generalized competition index of a primitive digraph［J］．Linear Algebra and its Applications，2012，436:86 －98．

［6］ Min Soo Sim，Hwa Kyung Kim．On generalized competition index of a primitive tournament［J］．Discrete Mathematics，2011，311:2657－2662．

［7］ Hwa Kyung Kim．A bound on the generalized competition index of a primitive matrix using Boolean rank［J］．Linear Algebra and its Applications，2011，435:2166 －2174．

［8］ Hwa Kyung Kim，Sang Hoon Lee．Generalized competition indices of symmetric primitive digraphs［J］．Discrete Applied Mathematics，2010，160:1583 －1590．