李林倩,方 炜

（1.山西农业大学信息学院,山西晋中030800；2.中北大学仪器与电子学院,山西太原030051）

一类特殊本原有向图的m－competition指数

李林倩1,方 炜2

（1.山西农业大学信息学院,山西晋中030800；2.中北大学仪器与电子学院,山西太原030051）

对一类含有两种不同圈长的本原有向图的m－competition指数进行了研究,根据图论知识,通过分析本原有向图D与本原有向图Dn－4,Dn－2之间的关系,结合本原有向图m－competition指数的定义,利用集合的运算给出了此类图的m－competition指数.

本原有向图；途径；m－competition指数

0 引言

设D为有向图,顶点集为V（D）,边集为E（D）,D中允许有环但不允许有重弧.本原有向图的研究,最早始于1950年Wielandt的工作,他给出了n阶本原有向图的一般性上界.文献［1,2］中介绍了本原有向图的定义,设D为有向图,如果存在正整数k,使得对于D中的任意两个顶点vi,vj（可以相同）,在D中都存在从vi到vj的k长途径,则称D为本原有向图.上述最小的k称为D的本原指数,记为exp（D）.

文献［3］中,M.Akelbek和S.Kirkland给出了本原有向图的scrambling指数的定义.D是n阶本原有向图.如果存在正整数k,对于D中任意顶点vi和vj,都存在顶点w∈V（D）,使得从vi和vj到w都有k长途径,满足上述条件的最小正整数k称为本原有向图D的scrambling指数,记作k（D）.

文献［4］中,从记忆通讯系统的背景,柳伯濂和黄宇飞对scrambling指数进行了推广,引入了广义scrambling指数.设D为n阶本原有向图,λ,μ∈Z＋,1≤λ,μ≤n.对于集合X⊆V（D）,定义（D）为最小的正整数l,使得存在μ个顶点w1,w2,…,wμ∈V（D）,对于∀x∈X,从x到wi都有l长途径（i＝1,2,…,μ）,则

分别称为本原有向图D的λ重下μ－scrambling指数和λ重上μ－scrambling指数.

本原有向图的m－competition指数是本原指数与scrambling指数的推广.文献［5］中,Hwa Kyung Kim和Sung Gi Park给出了本原……