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

李林倩,方 煒

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

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

李林倩1,方 煒2

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

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

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

0 引言

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

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

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

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

本原有向圖的m－competition指數(shù)是本原指數(shù)與scrambling指數(shù)的推廣.文獻［5］中,Hwa Kyung Kim和Sung Gi Park給出了本原有向圖的m－competition指數(shù)的概念.設D為n階本原有向圖,1≤m≤n,對于任意的頂點u,v∈V（D）,存在正整數(shù)m,在D中總能找到m個點,使得u,v到這m個點都存在k長途徑,上述k的最小值稱為D的m－competition指數(shù),記作km（D）.m－competition指數(shù)也稱為廣義competition指數(shù).

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

為了表達方便：

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

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

1 主要結論

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

圖1D

圖2Dn－4

定理設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)點.當vi是環(huán)點時,從vi經(jīng)過長途徑所能到達的點的個數(shù)至少為

圖3Dn－2

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

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

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

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

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

［2］徐俊明.圖論及其應用［M］.第2版.北京：中國科學技術大學出版社,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－）,女,山西長治人,碩士,山西農(nóng)業(yè)大學信息學院助教,主要從事組合數(shù)學的研究.