一个特殊本原有向图的广义competition及scrambling指数

张佩,高玉斌

(中北大学 数学系,山西 太原,030051)

1 相关知识与理论

设D是一个有向图(允许有环但不能有重复弧),D的一条长为l的途径是指连续的顶点序列 v1,v2,…,vl+1,对所有的 i=1,2,…,l,D中都有从 vi到 vi+1的弧。用记号表示从vi到vj的l长途径。另外,Dl是一个有向图,其中当且仅当在有向图D中

定义1[1]设有向图D,若存在1个正整数l,使得D中的任意2个顶点 x,y(可以相同),在D中都存在从x到y的l长途径,则称D是本原有向图,其中最小的正整数l称为本原指数,记为exp(D)。

引理1[1]有向图D是本原的充分必要条件是D为强连通,且D的所有圈长的最大公因子为1。

定义 2[2–3]设D是n阶本原有向图,如果存在正整数k,对D中任意顶点u和v,都存在顶点w∈V(D),使得从u和v到w都有k长途径,满足上述条件的最小正整数k,称为本原有向图D的scrambling指数,记为k(D)。

定义3[4]设D是n阶本原有向图,小的正整数l,使得存在μ个顶点w1,w2,…,wμ∈V(D),对于任意x∈X,从x到wi(i=1,2,…,μ)都有l长小途径,则分别称为本原有向图D的λ重下μ-s crambling 指数和λ重上 μ-scrambling 指数。特别地,当μ=1时,称 h(D,λ)和 k(D,λ)为有向图D的广义scramb-ling指数。

引理2[4]定义4[5]设D是n阶本原有向图及m为正整数,1≤m≤n。若存在正整数k,对任意2个顶点0,x能找到m个不同的顶点vi∈V(D)(i=1,2,…,m)使得在D中有则称满足上述条件的k为D的 m-c ompetition 指数,记为

引理3[5]当m=1时,k1(D)=k(D); 当m=n 时,

定义5[5]设D是n阶本原有向图,及顶点 x0,y0∈ V(D)与正整数若存在正整数k,能找到m个不同的顶点使得在D中有则称满足上述条件的k为点 x0,y0在D中的局部 m-c ompetition 指数,记为由此,可以得到

另外,本文用文献[6]中的记号 N+(Dk:x)表示点x在D中经过k长途径所能到达点的集合,即点x在中经过1长途径所能到达点的集合,而表示集合中顶点的个数。

2 主要结论

定理1 设D为如图1所示的 8n≥阶本原有向图,则有

证明 本原有向图D中含有1个 3n-圈,2个 4n-圈。

情形1 n+ m 为奇数且 m≤n-5。

图1 本原有向图D

情形3 m=n-3。

定理1得证。

定理2 设D是n阶本原有向图,如图1所示,则

由上可知,存在顶点 v2∈ V(DT),使得因此,存在一个顶点 v ∈ V(DT),使得

综上所述,h(D, λ) = t。定理2得证。

定理3 设D是n阶本原有向图,如图1所示,则有:

证明 设 u1,u2,…,um(1≤m≤n-4)是本原有向图D(图1)中 n-4 圈上的任意m个互异的点。首先证明考虑有向图 D(n-4),显然 u1,u2,…,um是有向图D(n-4)上的环点,故1)-n(m-1)≥1 。因此,在D(n-4)中存在一个顶点 w ∈ V(D(n-4))使得或者说D中存在一个顶点 w ∈ V(D)使得。因此,由 kX(D)的定义可知,

[1]Brualdi R A,Ryse H J.Combinatorial Matrix Theory [M].New York:Cambridge University Press,1991.

[2]Akelbek M,Kirkland S.Coefficients of ergodicity and scrambling index [J].Linear Algebra and Its Applications,2009,430:1 111–1 130.

[3]Liu B,Huang Y.The scrambling index of primitive digraphs [J].Computers and Mathematics with Applications,2010,60:706–721.

[4]Huang Y,Liu B.Generalized scrambling indices of a primitive digraphs [J].Linear Algebra and Its Applications,2010,433:1 798–1 808.

[5]Kim H K.Generalized competiton index of a primtitive digraph [J].Linear Algebra and Its Applications,2010,433:72–79.

[6]Kim H K,Pank S G.A bound of generalized competiton index of a primtitive digraph [J].Linear Algebra and Its Applications,2012,436:86–98.