李林倩,方 煒

（1.山西農(nóng)業(yè)大學(xué)信息學(xué)院,山西晉中030800；2.中北大學(xué)儀器與電子學(xué)院,山西太原030051）

一類特殊本原有向圖的m－competition指數(shù)

李林倩1,方 煒2

（1.山西農(nóng)業(yè)大學(xué)信息學(xué)院,山西晉中030800；2.中北大學(xué)儀器與電子學(xué)院,山西太原030051）

對(duì)一類含有兩種不同圈長(zhǎng)的本原有向圖的m－competition指數(shù)進(jìn)行了研究,根據(jù)圖論知識(shí),通過(guò)分析本原有向圖D與本原有向圖Dn－4,Dn－2之間的關(guān)系,結(jié)合本原有向圖m－competition指數(shù)的定義,利用集合的運(yùn)算給出了此類圖的m－competition指數(shù).

本原有向圖；途徑；m－competition指數(shù)

0 引言

設(shè)D為有向圖,頂點(diǎn)集為V（D）,邊集為E（D）,D中允許有環(huán)但不允許有重弧.本原有向圖的研究,最早始于1950年Wielandt的工作,他給出了n階本原有向圖的一般性上界.文獻(xiàn)［1,2］中介紹了本原有向圖的定義,設(shè)D為有向圖,如果存在正整數(shù)k,使得對(duì)于D中的任意兩個(gè)頂點(diǎn)vi,vj（可以相同）,在D中都存在從vi到vj的k長(zhǎng)途徑,則稱D為本原有向圖.上述最小的k稱為D的本原指數(shù),記為exp（D）.

文獻(xiàn)［3］中,M.Akelbek和S.Kirkland給出了本原有向圖的scrambling指數(shù)的定義.D是n階本原有向圖.如果存在正整數(shù)k,對(duì)于D中任意頂點(diǎn)vi和vj,都存在頂點(diǎn)w∈V（D）,使得從vi和vj到w都有k長(zhǎng)途徑,滿足上述條件的最小正整數(shù)k稱為本原有向圖D的scrambling指數(shù),記作k（D）.

文獻(xiàn)［4］中,從記憶通訊系統(tǒng)的背景,柳伯濂和黃宇飛對(duì)scrambling指數(shù)進(jìn)行了推廣,引入了廣義scrambling指數(shù).設(shè)D為n階本原有向圖,λ,μ∈Z＋,1≤λ,μ≤n.對(duì)于集合X?V（D）,定義（D）為最小的正整數(shù)l,使得存在μ個(gè)頂點(diǎn)w1,w2,…,wμ∈V（D）,對(duì)于?x∈X,從x到wi都有l(wèi)長(zhǎng)途徑（i＝1,2,…,μ）,則

分別稱為本原有向圖D的λ重下μ－scrambling指數(shù)和λ重上μ－scrambling指數(shù).

本原有向圖的m－competition指數(shù)是本原指數(shù)與scrambling指數(shù)的推廣.文獻(xiàn)［5］中,Hwa Kyung Kim和Sung Gi Park給出了本原有向圖的m－competition指數(shù)的概念.設(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－competition指數(shù),記作km（D）.m－competition指數(shù)也稱為廣義competition指數(shù).

另外,根據(jù)三者定義不難得到n階本原有向圖的m－competition指數(shù)與本原指數(shù),scrambling指數(shù)之間的關(guān)系：k（D）＝k1（D）≤k2（D）≤…≤kn（D）＝exp（D）.

為了表達(dá)方便：

2）RDt｛x｝表示從集合D中的頂點(diǎn)x出發(fā),經(jīng)過(guò)t長(zhǎng)途徑所能到達(dá)的點(diǎn)的集合,t為非負(fù)整數(shù).

3）｜RDt｛x｝｜表示從集合D中的頂點(diǎn)x出發(fā),經(jīng)過(guò)t長(zhǎng)途徑所能到達(dá)的點(diǎn)的個(gè)數(shù).

1 主要結(jié)論

本文主要主要研究了一類特殊的本原有向圖D（含有兩個(gè)n－4圈和一個(gè)n－2圈,如圖1所示）的mcompetition指數(shù)見(jiàn)圖1,圖2.

圖1D

圖2Dn－4

定理設(shè)D為n（n≥9,n≡1（mod2））階本原有向圖（如圖1所示）,則有向圖D的m－competition指數(shù)為：

證明：Case1n＋m是偶數(shù),且m≥3.

由D的本原性可得Dn－4（如圖2所示）是本原的.

在Dn－4中,令Cn－2＝｛v1,v2,…vn－3,vn－2｝,其中｛v2,v3,…vn－3｝是環(huán)點(diǎn).當(dāng)vi是環(huán)點(diǎn)時(shí),從vi經(jīng)過(guò)長(zhǎng)途徑所能到達(dá)的點(diǎn)的個(gè)數(shù)至少為

圖3Dn－2

Case2n＋m是奇數(shù),且6≤m≤n－3.

由D的本原性可得Dn－2（如圖3所示）是本原的.

在Dn－2中,令Cn－4＝｛v2,v3,…vn－3｝,且Cn－4中的頂點(diǎn)都是環(huán)點(diǎn).當(dāng)vi是環(huán)點(diǎn)時(shí),從vi經(jīng)過(guò)n長(zhǎng)途徑所能到達(dá)的點(diǎn)的個(gè)數(shù)至少為

在D中,點(diǎn)集V（D）＼｛vn－2,vn－3｝中的任意一個(gè)頂點(diǎn)經(jīng)過(guò)1長(zhǎng)途徑都能到達(dá)環(huán)點(diǎn)｛v2,v3,…vn－3｝,而且

［1］邵嘉裕.對(duì)稱本原矩陣的指數(shù)集［J］.中國(guó)科學(xué)（A輯）,1986（9）：931－939

［2］徐俊明.圖論及其應(yīng)用［M］.第2版.北京：中國(guó)科學(xué)技術(shù)大學(xué)出版社,2005

［3］Mahmud Akelbek,Steve Kirkland.Coefficients of ergodicity and the scrambling index［J］.Linear Algebra and its Applications,2009,430：1111－1130

［4］Yufei Huang,Bolian Liu.Generalized scrambling indices of a primitive digraph［J］.Linear Algebra and its Applications,2010,433：1798－1808

［5］Hwa Kyung Kim.Generalized competition index of a primitive digraph［J］.Linear Algebra and its Applications,2010,433：72－79

The Competition Index of A Special Class of Primitive Digraphs

LI Linqian1,FANG Wei2
（1.College of Information,Shanxi Agricultural University,Jinzhong 030800；2.School of Instrument and Electronic,North University of China,Taiyuan 030051,China）

A class of two different cycle length of primitive digraphs are discussed.According to graph theory,by analyzing the relationship between the primitive digraph D and the primitive digraphDn－4,Dn－2and combining with the definition of the m－competition index of a primitive digraph,the exponent of this special class of primitive digraphs is given through the set operations.

the primitive digraph；walk；m－competitionindex

1672－2027（2016）04－0045－04

O157.5

A

2016－09－11

李林倩（1987－）,女,山西長(zhǎng)治人,碩士,山西農(nóng)業(yè)大學(xué)信息學(xué)院助教,主要從事組合數(shù)學(xué)的研究.