一类本原有向图的m-competition指数及广义scrambling指数

迹为零的对称本原矩阵的scrambling指数张月梅;陈佘喜【摘要】设A为n阶本原矩阵,若存在正整数k,使得对于Ak的任意两行,都在某一列上的元素为正,这样的最小正整数称为本原矩阵A的scrambling指数.采用图理论来研究对称本原A的scrambling指数.解决了迹为零的对称本原矩阵的scrambling指数的上确界问题,进而得到了其指数集,并完全刻划了这类矩阵的极矩阵.【期刊名称】《河南科学》【年(卷),期】2011(029)002【总页数】3页(P136-138)【关键词】本原矩阵;scrambling指数;本原指数;有向图【作者】张月梅;陈佘喜【作者单位】湖南科技大学数学与计算科学学院,湖南湘潭411201;湖南科技大学数学与计算科学学院,湖南湘潭411201【正文语种】中文【中图分类】O157一个n阶非负矩阵A称为本原矩阵，如果存在某个自然数k，使得Ak>0，这样的自然数中的最小者称为A的本原指数，记作exp（A）.在文献［1］中，Akelbek M和Kirkland S从随机矩阵的第二大特征值入手，给出了本原矩阵的scrambling指数的定义.对于本原矩阵A，存在自然数k，使得Ak的任意两行，都存在同一列，在这一列上两行元素同为正，这样的自然数中的最小者称为A的scrambling指数，记作k（A）.在文献［1-2］中，Akelbek M和Kirkland S给出了伴随有向图的围长为s的n 阶本原矩阵的scrambling指数的上确界，并完全刻画了该类本原矩阵的极矩阵，特别地，还解决了一般本原矩阵类的scrambling指数上确界和极矩阵问题.文献［3］研究了对称本原矩阵的scrambling指数问题.本文将考虑迹为零的对称本原矩阵的scrambling指数集Kn和极矩阵问题.众所周知，在研究矩阵的组合性质时，图论技巧是一个广泛使用而行之有效的方法. 设D是本原有向图，则存在自然数k，对任意一对顶点x、y，一定存在一个顶点w，使成立.这样的自然数中的最小者，称为D的scrambling指数，记作k（D）.设x，y∈V（D），则x、y之间的局部scrambling指数为，w∈V（D）｝，很明显，k（D）=max｛kx（yD）│x，y∈V（D），x≠y｝.设G是一个无向图，若我们把G的每一条边ij（i≠j）换成二条有向弧（i，j）和（j，i），所得到的有向图记作DG，称为G的对称有向图.显然G和DG有相同的本原性，且它们为本原时，有相同的scrambling指数.设A是一个n阶非负矩阵，其伴随有向图是D（A）.若A是对称矩阵，则D（A）是对称有向图，从而A 对应了一个无向图G（A）.另外，由定义我们容易知道，非负矩阵A是本原的当且仅当它的伴随有向图D（A）是本原的，此时，exp（A）=exp（D（A）），k （A）=k（D（A））. 因此，研究对称本原矩阵 scrambling指数刻划问题完全等价于研究本原无向图的scrambling指数刻划问题.而本文给出的对对称本原矩阵类scrambling指数集的刻划，事实上也就是对对称本原有向图类或本原无向图的scrambling指数集的刻划.为方便起见，本文下面将全部用图论的语言叙述，未定义的知识文献［4］.设 D=（V，E）是强连通有向图，u∈V，X⊆V.定义 d（u，X）=min｛d（u，x）│x∈X｝. 若u∈X，则 d（u，X）=0.引理1[4]D是n阶对称本原有向图，Cr为D中长为r的奇圈.u，v是D的任意两个顶点，则有：引理2[5-6]无向图G是本原的充要条件是G满足：①G是连通的；②G至少含一条奇圈.定理3 D是n阶对称本原有向图，则有：k（D）≤n-2.设Pm，Q，H均为无向图，其中Pm是一条长为m的路.C3是长为3 的圈，K1，m是星图.定义G=G1×H，G1=Q◦Pm.其中Q◦Pm表示将图Q中的最小度点与路Pm的最小度点粘合，G=G1×H，表示将图G1中的最小度点与H的最大度点粘合而成. 4）若i∈｛1，2｝，j∈｛4，5，…，n｝.i=1 和 i=2 时两种情形完全相同，不妨假设 i=1.定理4 G为n阶本原无向图，n为自然数且n≥3，则k（G）=n-2的充分必要条件是：G同构于.证明充分性：由定理1可知：k（）=n-2.必要性设G为n阶无环本原无向图，k（G）=n-2.1）G中含有长为3的圈.若G中无长为3的圈，由引理2知，G中至少含一条奇圈，设其长为r，r≥5.由引理1知，由引言知：k（D）≤n-3. 所以，G中含有长为3的圈.2）G 中存在一点 x，使得 d（x，V（C3））＝n-3. 对任意x∈V（G）有 d（x，V（C3））＜n-3. 由引理 1 知，与题设矛盾.由上述（1）（2）知：G中存在一个支撑子图G*同构于Gn-3n .3）不妨假设G*如图3所示.V（G）＝V（G*），假设存在 e＝kikj∈E（G），但是 e∉E（G*）.①若 ki，kj∈｛k3，k4，…，kn｝，不妨假设 j＞i，当 j＝i＋1 时 G 有重边 kikj；当j≠i＋1 时，与 2）矛盾.②若ki∈｛k1，k2｝，kj∈｛k4，k5，…，kn｝.则只可能e＝k1k4或e＝k2k4，否则与 2）矛盾. 不妨设 e＝k1k4，则 G 中存在一个异于 C3的奇圈C′3＝k1k3k4. 由图明显可知：不存在点x∈V（G），使得 d（x，V（））＝n-3 成立，由引理1 得 k（G）＜n-2. 因此：G=G*.由（1～3）得：k（G）＝n-2 时 G 同构于 Gnn-3.Key words：primitive matrix；scrambling index；primitive exponent；digraph【相关文献】［1］ Akelbek M，Kirkland S.Coefficients of ergodicity and the scrambling index［J］.Linear Algebra Appl，2009（430）：1111-1130.［2］ Akelbek M，Kirkland S.Primitive digraphs with the largest scrambling index［J］.Linear Algebra Appl，2009（430）：1099-1110.［3］ Chen Shexi，Liu Bolian.The scrambing index of symmetric primitive matrices［J］.Linear Algebra Appl，2010（433）：1110-1126.［4］徐俊明.图论及其应用［M］.2版.北京：中国科学技术大学出版社，2005.［5］ Shao Jiayu.The exponent set of symmetric primitive matrices［J］.Scientia Sinica （Ser.A），1987（30）：348-358.［6］ Brualdi R A，Shao J.Generalized exponent set of primitive symmetric digraphs ［J］.Drscrete Appl Math，1997（74）：275-293.Abstract：The scrambing index of a primitive matrix A is the smallest positive integer k such that any two rows of Akhave at least one positive element in a coincident position.In this paper，the scrambing index of symmetric primitive matrices by using graph theory were investigated.The upper bound for the scrambing index of zero-trace symmetric primitive matrices was obtained.Moreover，the scrambing index set for this class of matrices was determined，and characterize completely the extremal matrices.。

本原极小强连通有向图的重下scrambling指数
尹作香;邵燕灵
【期刊名称】《河南师范大学学报：自然科学版》
【年(卷),期】2012(40)6
【摘要】利用图论、数论的相关知识,分析了图中每一点经过t长途径所到达的点的集合,再结合scrambling指数和重下scrambling指数的定义刻画了本原极小强连通有向图的重下scrambling指数的界.
【总页数】4页(P8-11)
【关键词】scrambling指数;重下scrambling指数;本原有向图;途径;界
【作者】尹作香;邵燕灵
【作者单位】中北大学数学系
【正文语种】中文
【中图分类】O157.5
【相关文献】
1.围长为2的奇数阶本原极小强连通有向图的1-指数集 [J], 胡亚辉;王晋
2.围长为2的奇数阶本原极小强连通有向图的1-指数集 [J], 胡亚辉;王晋
3.n阶本原极小强连通有向图k-指数的最小值 [J], 胡亚辉;曾艳辉
4.极小强连通本原有向图的非本原指数的一个新下界 [J], 胡志庠
5.极小强连通本原有向图的本原指数集 [J], 邵嘉裕
因版权原因，仅展示原文概要，查看原文内容请购买。

一个 n 阶本原有向图的 m－competition 指数刘彩锋;高玉斌【摘要】In this paper, a primitive digraph D of order n with one (n -1) -cycle and one (n -2) -cycle is considered.According to the structure of D , we draw up the primitive digraphsDn-2 andDn-3 .Then the sets and the numbers of vertexes, which are formed by each vertex passing a walk of length k in the primitive digraphs D , Dn-2 and Dn-3 are discussed respectively.In addition, based on the definition of m -competition index, we work out the m -competition index of the primitive digraph.%文中讨论了一个含有一个n－2圈和一个n－3圈的n阶本原有向图D 。

由D的结构得到本原图Dn－2和Dn－3，然后分别对本原图D ， Dn－2和Dn－3中任一点经过k长途径所到达的顶点的集合以及顶点的个数进行分析，再结合m －competition指数的定义，得到这个本原图的m －competition指数。

【期刊名称】《商丘师范学院学报》【年(卷),期】2015(000)009【总页数】6页(P1-6)【关键词】有向图;本原图;m -competition指数【作者】刘彩锋;高玉斌【作者单位】中北大学数学系，山西太原030051;中北大学数学系，山西太原030051【正文语种】中文【中图分类】O157.5近年来, 本原有向图的scrambling指数和m-competition指数是学者们的一个新兴研究分支.2009年,Akelbek和Kirkland在文献[2]中提出了本原有向图的scrambling指数的概念.2010年, Hwa Kyung Kima将本原图的本原指数和scrambling指数推广到m-competition指数(也叫广义competition指数), 并在文献[3]中给出m-competition指数的定义, 随后, 他找到了本原矩阵的m-competition指数的上界, 同时确定了最小圈长为s的本原图的m-competition指数的上界, 而文中讨论了一个特殊本原有向图的m-competition指数.设D=(V,E)表示一个有向图, 其中顶点集V=V(D), 弧集E=E(D), 并且D为n阶, 即|V(D)|=n, D中允许有环但不允许有重弧.D中一条x到y的k长途径是指含有k条弧的一个序列(x,x1),(x1,x2),…,(xk-1,y), 其中这k条弧都属于E(D), 并且这些弧的端点都属于V(D), 简记为.如果D为有向图, 则Dl也为有向图, 定义Dl如下：V(Dl)=V(D),E(Dl)={(x,y)|在D中有[1].定义1[2] 设D为n阶有向图, 如果存在正整数m, 使得对于D中任意两点x,y, 从x到y都有m长的途径, 则称D为本原有向图, 或称本原图.有向图D是本原图的充要条件是D为强连通图且D中所有圈长的最大公因子为1[1].如果D为本原图, 则Dl也为本原图.D为强连通图是指D为有向图且任意顶点u,v∈V(D), 既存在u到v的途径, 又存在v到u的途径[1].定义2[3] 设D为n阶本原图, 对于正整数m(1≤m≤n), 如果存在正整数k, 对于D 中任意一对顶点x,y, 总能在D中找到m个不同的点, 使得在D中x和y到这m个点都有k长途径, 则称满足上述条件的最小正整数k为D的m-competition指数, 也叫做广义competition指数, 记为km(D).如果上述D中顶点x,y已事先确定，则称此定义为点x,y在D中的局部m-competition 指数, 记为由上述定义可得(D:x,y).m=n时, kn(D)=exp(D).文中符号N+(Dk:x)表示点x在D中经过k长途径所到达点的集合, |N+(Dk:x)|表示集合中顶点的个数.N+(Dk:x,y)表示顶点x和y在D中经过k长途径所到达公共点的集合, 即N+(Dk:x,y)=N+(Dk:x)∩N+(Dk:y).设D为一个本原图, C为D中的一个圈, 则用l(C)来表示C的圈长.文中本原有向图中的顶点上的小圆圈表示一个环, 即该顶点是一个环点, 环的方向可以任意, 既可以顺时针也可以逆时针.定理设n阶(n≥12)本原图D如图1所示，D中含有一个n-2圈和一个n-3圈, 则对于正整数m(1≤m≤n), D的m-competition指数为证明情形1 1≤m≤n-5且n+m为奇数.首先证明对任意x,y∈V(D)都有(n-2).子情形1 对任意x,y∈V(D)且x,y≠vn-3和vn-4时,存在vi,vj∈V(D)(4≤i,j≤n-2), 在本原图Dn-2中, 顶点集{v4,v5,…,vn}构成一个n-3圈记为C1, 则l(C1)=n-3, 且vi,vj(4≤i,j≤n-2)均为环点, 所以vi,vj经过长途径所到达的顶点个数均至少为个，从而则vi,vj(4≤i,j≤n-2)在Dn-2中经过长途径至少含有m个公共点, 所以且x,y≠vn-3和vn-4.在Dn-2中为环点, vj在Dn-2中经过长途径所到达的顶点个数至少为个，并且这个点都是n-3圈C1上的点, 从而即在D中vn-3和y经过长途径至少含有m个公共点, 因此所以由上同理可得(n-2).子情形3 当x,y等于vn-3和vn-4时, 不妨设x=vn-3,y=vn-4时, 由上(1)(2)式可所以即(n-2).综上3个子情形可得(n-2).下面证(n-2).在Dn-2中取特殊点v1和当m=1时φ, 当m≥2时,即在D中v1和经过长途径所到达的公共点个数小于m, 从而(n-2).综上可得(n-2).情形2 1≤m≤n-4且n+m为偶数.首先证明(n-3).子情形1 对任意x,y∈V(D)且x,y≠v1,vn-3,vn-2, 存在vi,vj∈V(D), 其中由本原图D可得本原图Dn-3如图3.在Dn-3中, 顶点集{vn-2,vn-3,…,v3,v2,v1}形成一个n-2圈记为C2, 与情形1中的子情形1类似可得且x,y≠v1,vn-3,vn-2.子情形2 对任意x,y∈V(D)且x,y中有一个等于v1或vn-3或vn-2时, 不妨设x=v1,与情形1中的子情形2类似可得(n-3). 当x=vn-3和x=vn-2时, 同样可得(n-3). 子情形3 对任意x,y∈V(D)且x,y等于v1,vn-3和vn-2中任意两个时, 有3种情况x=v1,y=vn-3和x=v1,y=vn-2和x=vn-3,y=vn-2, 与情形1中的子情形3类似可得(n-3).接下来证明(n-3).在Dn-3中取特殊点v1和当m=1时φ, 当m≥2时,即在D中v1和经过长途径所到达的公共点个数小于m, 从而(n-3).综上可得(n-3).情形3 m=n-3.在Dn-2中, N+((Dn-2)n-4:v1)=V(D)\{vn-2},N+((Dn-2)n-4:v2)=V(D)\{v1,vn-1}, N+((Dn-2)n-4:v3)=V(D)\{v2,vn}, N+((Dn-2)n-4:v4)=V(D)\{v3},N+((Dn-2)n-4:vj)=V(D)(5≤j≤n-2), N+((Dn-2)n-4:vn-1)=V(D)\{v1,vn-1},N+((Dn-2)n-4:vn)=V(D)\{v2,vn}.即在D中,N+(D2+(n-2)(n-4):v1)=V(D)\{v2,vn},N+(D2+(n-2)(n-4):v2)=V(D)\{v3},N+(D2+(n-2)(n-4):vi)=V(D)(3≤i≤n-4),N+(D2+(n-2)(n-4):vn-3)=V(D)\{vn-2}∪V(D)\{v1,vn-1}=V(D),N+(D2+(n-2)(n-4):vn-2)=V(D)\{v1,vn-1}∪V(D)\{v2,vn}=V(D),N+(D2+(n-2)(n-4):vn-1)=V(D)\{v3}, N+(D2+(n-2)(n-4):vn)=V(D).则任意x,y∈V(D), 在D中经过2+(n-2)(n-4)长途径至少含有n-3个公共点, 从而kn-3(D:x,y)≤2+(n-2)(n-4).下面证.取特殊点v1和v2,在D中由上知所以N+(D1+(n-2)(n-4):v1,v2)=V(D)\{v1,vn-1}∩V(D)\{v2,vn}=V(D)\{v1,v2,vn-1,vn}, 即在D中v1和v2经过1+(n-2)(n-4)长途径所含公共点个数小于n-3, 从而kn-3(D)>1+(n-2)(n-4). 综上所述kn-3(D)=2+(n-2)(n-4).情形4 m=n-2.在D中,. 用情形3类似方法可得, 任意x,y∈V(D), x,y在D中经过3+(n-2)(n-4)长途径至少含有n-2个公共点, 从而kn-2(D:x,y)≤3+(n-2)(n-4).下面证kn-2(D)>2+(n-2)(n-4).V(D)\{v3}, 所以N+(D2+(n-2)(n-4):v1,v2)=V(D)\{v2,vn}∩V(D)\{v3}=V(D)\{v2,v3,vn}, 即在D中v1和v2经过2+(n-2)(n-4)长途径所到达的公共点的个数小于n-2, 从而kn-2(D)>2+(n-2)(n-4). 综上所述kn-2(D)=3+(n-2)(n-4).情形5 m=n-1.在D中,在Dn-3中,N+((Dn-3)n-3:v1)=V(D)\{v1,vn-1},N+((Dn-3)n-3:v2)=V(D)\{v2,vn}, N+((Dn-3)n-3:v3)=V(D)\{v3}=N+((Dn-3)n-3:vn),N+((Dn-3)n-3:vj)=V(D)(4≤j≤n-2), N+((Dn-3)n-3:vn-1)=V(D)\{v2,vn}.即在D中, N+(D2+(n-3)(n-3):v1)=V(D)\{v3},N+(D2+(n-3)(n-3):vi)=V(D)(2≤i≤n-4),N+(D2+(n-3)(n-3):vn-3)=V(D)\{v1,vn-1}∪V(D)\{v2,vn}=V(D),N+(D2+(n-3)(n-3):vn-2)=V(D)\{v2,vn}∪V(D)\{v3}=V(D),N+(D2+(n-3)(n-3):vn-1)=V(D)=N+(D2+(n-3)(n-3):vn).则任意x,y∈V(D), 在D中经过2+(n-3)(n-3)长途径至少含有n-1个公共点, 从而kn-1(D:x,y)≤2+(n-3)(n-3).下面证取特殊点由上知所即在D中v1经过1+(n-3)(n-3)长途径所到达的点的个数小于n-1, 从而kn-1(D)>1+(n-3)(n-3). 综上所述kn-1(D)=2+(n-3)(n-3).情形6 m=n.在D中,用情形5类似方法可得, 任意x,y∈V(D), x,y在D中经过3+(n-3)(n-3)长途径可以到达图中所有的n个点, 从而kn(D:x,y)≤3+(n-3)(n-3).下面证kn(D)>2+(n-3)(n-3).取特殊点由情形5知N+((Dn-3)n-3:v3)=V(D)\{v3}, 所以N+(D2+(n-3)(n-3):v1)=V(D)\{v3}, 即在D中v1经过2+(n-3)(n-3)长途径所到达的点的个数小于n, 从而kn(D)>2+(n-3)(n-3). 综上所述kn(D)=3+(n-3)(n-3). 证毕.【相关文献】[1] Brualdi R A, Ryser H binatorial Matrix Theory [M].Cambridge University Press, 1991.[2] Liu B L, Huang Y F.The scrambling index of primitive digraphs[J].Computers and Mathematics with Applications, 2010, 60(3):706-721.[3] Kim H K.Generalized competition index of a primitive digraph [J].Linear Algebra and its Applications,2010, 433 (1):72-79.[4] Akelbek M, Kirkland S.Coefficients of ergodicity and the scrambling index [J].Linear Algebra and its Applications,2009,430(4):1111-1130.[5] Shao Y L, Gao Y B.The m-competition indices of symmetric primitive digraphs with loop[J].Ars Combination, 2013, 108:217-223.。

一个本原有向图的 scrambling 指数和广义 scrambling 指数樊瑞;高玉斌【期刊名称】《长春师范学院学报（自然科学版）》【年(卷),期】2014(000)004【摘要】This paper studies a primitive digraph with three cycles of order n (let n≥7 and n = 2s - 1 ) which contains one n - cycle and two s - cycles. Based on the definitions and correlative theory of scrambling index and generalized scrambling indices, the scramb-ling index and generalized scrambling indices of the primitive digraph are obtained.%本文研究一个含有三个圈的n(n≥7且 n =2s -1)阶本原有向图，其中包含一个 n 圈和两个 s 圈。

根据 scrambling 指数和广义 scrambling 指数的定义和相关理论，得出该图的scrambling 指数和广义 scrambling 指数。

【总页数】4页(P13-16)【作者】樊瑞;高玉斌【作者单位】中北大学数学系，山西太原 030051;中北大学数学系，山西太原030051【正文语种】中文【中图分类】O157.5【相关文献】1.一个本原有向图的scrambling指数和广义scrambling指数 [J], 樊瑞;高玉斌2.一个特殊本原有向图的scrambling指数及广义scrambling指数 [J], 张佩;王卓宇;高玉斌3.一类本原有向图的scrambling指数和广义scrambling指数 [J], 李林倩;李星星4.一个本原有向图的scrambling指数和广义scrambling指数 [J], 樊瑞;高玉斌;5.一个特殊本原有向图的Scrambling指数和广义Scrambling指数 [J], 张佩;王新年;高玉斌因版权原因，仅展示原文概要，查看原文内容请购买。

一类本原有向图m-competition指数的刻画申佳;高玉斌【摘要】本文对一类含有一个n圈和两个s圈的n阶本原有向图的m-competition指数进行了研究,通过分析本原有向图的特点,结合图论原理并根据本原有向图的本原指数,scrambling指数和m-competition指数的定义,综合运用已知文献里提到的证明方法,给出了一类含有一个n圈和两个s圈的n阶本原有向图的m-competition指数,其中n=2s-1,两个s圈有l(1≤l≤s-1)个公共顶点.【期刊名称】《山西师范大学学报（自然科学版）》【年(卷),期】2015(029)004【总页数】6页(P1-6)【关键词】本原有向图;本原指数;scrambling指数;m-competition指数【作者】申佳;高玉斌【作者单位】中北大学理学院,山西太原030051;中北大学理学院,山西太原030051【正文语种】中文【中图分类】O157.51 预备知识设有向图D，若存在一个正整数l，使得D中任意两个顶点x,y(可以相同)，在D 中都存在从x到y的l长途径，则称D是本原有向图，其中最小的正整数l称为D的本原指数，记为exp(D).D是本原有向图的充分必要条件是D强连通，且D的所有圈长的最大公因子为1[1].用表示从x到y有l长的途径.定义Dl为一个本原有向图, 其中V(Dl)=V(D), (vi,vj)∈E(Dl)当且仅当在D中有在2009年, Akelbek和Kirkland在文献[1]中提出了本原图的scrambling指数的概念，本原有向图D的scrambling指数是最小的正整数k, 对任意一对顶点u和v，都存在w∈V(D),使得从u和v到w都有k长途径，这样的k称为本原有向图D的scrambling指数，记为k(D).2010年, Hwa Kyung Kim在文献[2]中提出了本原图的m-competition指数这一概念.设D是n阶本原有向图,1≤m≤n, 若存在正整数k, 使得对于任意的顶点u,v∈V(D)，在D中总能找到m个不同顶点，使得u,v经过k长途径都能到这m 个点，上述k的最小值称为D的m-competition指数，记作km(D). 如果上述顶点u,v∈V(D)已给定，则满足上述条件的最小的k称为点x,y在D中的局部m-competition指数,记为km(D:u,v).对于n阶本原有向图D, 显然有k(D)=k1(D)≤k2(D)≤…≤kn(D)=exp(D).近年来, 对scrambling指数和m-competition指数的研究已取得很多成果, 如在文献[3]中, 作者获到了本原有向图scrambling指数的上界, 并找到了取得上界的极图; 文献[4]中, 作者研究了对称本原有向图的scrambling指数; 文献[5]中, 作者研究了仅含两个圈的本原有向图的scrambling指数; 文献[6]中，作者研究了对称含环本原图的m-competition指数问题.文中用文献[7]中的记号N+(Dk:x)表示点x在D中经过k长途径所到达点的集合, 用|N+(Dk:x)|表示集合中点的个数.N+(Dk:x,y)=N+(Dk:x)∩N+(Dk:y).deg+(x)表示顶点x的出度.2 主要结论设n≥5为奇数, 用D表示由全体恰含一个n圈和两个s圈的n阶有向图所构成的集合, 显然, 对任意D∈D, D是本原的. 下面我们将给出D中所有图的m-competition指数(1≤m≤n).定理1 设D∈D, 如图1所示, 当s为奇数时, 则对任意1≤m≤n, 有其中,l表示D中两个s圈的公共顶点个数.证明证明过程中需用到有向图Ds和Dn,其中图1 本原有向图DFig.1 Primitive digraph DV(Ds)=V(D)E(Ds)= {(vi,vi+s)|i=1,2,…,s-1}∪{(vi,vi)|i=1,2,…,n-l+1}∪{(vi,vi-s+1)|i=s,s+1,…,n}∪{(vi,vi-s)|i=s+1,…,n-l+1}V(Dn)=V(D)E(Dn)= {(vi,vi)|i=1,2,…,n}∪{(vi,vi-1)|i=2,3,…,n-l+1}∪{(vi,vi+s-1)|i=1,2,…,s}∪{(vi,vi-s)|i=s+1,…,n}∪{(vi,vi-s-1)|i=s+2,…,n-l+1}情形1 m=1时, 一方面证明情形1.1 l=1，在图Dn中, 可以得到故对于任意的i≠j 都有成立, 所以情形图1中, 取{v1,v2,…,vs,v1}圈记为C1, 则所有顶点可分为两部分, 一部分为不能经过l-1长途径到达C1上的顶点集{vs+1,…,vn-2l+2}, 记为V1, 顶点V1集经过l-1长途径到达的顶点集为V′={vs+l,…,vn-l+1}. 另一部分为可经过l-1长途径到达C1上的顶点集V(D)-V1, 记为V2.情形1.2.1 若vi,vj∈V2, 在D中总有和而在图Dn中, V2中的点均为环点且C1仍为一个s圈, 令C′=Dn[{V(C1)}]为Dn的一个导出子图, 则在图C′中有又因为C′⊂Dn, 因此情形1.2.2 若vi,vj∈V1, 在D中总有和而在图Dn中, V′中的点依次相连均为环点且deg+(vx)≥2(与vx关联的其他边的另一个顶点也依次相连且为V2中的顶点)，因此同理所以情形1.2.3 若vi∈V2,vj∈V1, 在D中总有和而在图Dn中, 所有点均为环点且有而对于任意的vx,vy,{vy-1,vy-2,…,vx,vy-1} 总能形成一个s圈, 因此所以综上情形1.3 ≤l≤s-1,图1中的顶点均可经过l-1长途径到达C1, 根据情形1.2.1, 可以得到综合以上三种情形, 即任取vi,vj∈V(D), vi,vj在D中经过长途径到达的公共点个数至少有1个, 根据m-competition指数的定义, 因此另一方面证明取点vn-l+2和点由图1可知,∅, 因此综上,情形2 m≥3且m为奇数时, 一方面证明图1中所有顶点均可经过l-1长途径到达任意一个s圈, 任意一个s圈上的顶点集{v1,v2,…,vn-l+1}记为V1(特殊地，l=1时, V(D)=V1), 则对于任意vi,vj∈V(D), 在D中总有和而在本原有向图Ds中, V1中的点均为环点且顶点集{v1,v1+s,v2,v2+s…,vs-1,vn,v1}形成一个n圈, 所以即任取两点vi,vj∈V(D), vi,vj在D中经过长途径到达的公共点个数至少为m. 根据m-competition指数的定义，因此另一方面证明当m=3+4k时, 取点vn-l+2和点由图1可知当m=5+4k时, 取点vn-l+2和点由图1可知因此综上,情形3 m=2+4k,4+4k且时, 一方面要证明图1中所有顶点均可经过l-1长途径到达任意一个s圈, 任意一个s圈上的顶点集{v1,v2,…,vn-l+1}记为V1(特殊地，l=1时, V(D)=V1), 则对于任意vi,vj∈V(D), 在D中总有和从而也有和而在本原有向图Ds中, V1中的点均为环点且顶点集{v1,v1+s,v2,v2+s,…,vs-1,vn,v1}形成一个n 圈, 所以即任取两点vi,vj∈V(D), vi,vj在D中经过长途径到达的公共点个数至少为m. 根据m-competition指数的定义，因此另一方面, 证明取点vn-l+2和点由图1可知即点vn-l+2和点在D中经过长途径到达的公共点个数为m-1.所以综上,综合上述三种情形,定理得证.定理2 设D∈D, 如图1所示, 当s为偶数时, 则对任意1≤m≤n, 有其中,l表示D中两个s圈的公共顶点个数.证明情形1:m=2时, 一方面证明情形1.1:l=1, 根据定理1的情形1.1类似的方法可以得到情形图1中, 取{v1,v2,…,vs,v1}圈记为C1, 则所有顶点可分为两部分, 一部分为不能经过l-1长途径到达C1上的顶点集{vs+1,…,vn-2l+2}, 记为V1, 顶点集V2经过l-1长途径到达的顶点集为V′={vs+l,…,vn-l+1}. 另一部分为可经过l-1长途径到达C1上的顶点集V(D)-V1, 记为V2.情形1.2.1:若vi,vj∈V2, 在D中总有和而在图Dn中, V2中的点均为环点且C1仍为一个s圈, 令C′=Dn[{V(C1)}]为Dn的一个导出子图, 则在图C′中有又因为C′⊂Dn, 因此情形1.2.2 若vi,vj∈V1, 在D中总有和而在图Dn中, V′中的点依次相连均为环点且deg+(vx)≥2(与vx关联的其他边的另一个顶点也依次相连且为V2中的顶点), 因此同理, 所以情形1.2.3: 若vi∈V2,vj∈V1, 在D中总有和而在图Dn中, 所有点均为环点且有而对于任意的vx,vy, {vy-1,vy-2,…,vx,vy-1}总能形成一个s圈, 因此所以综上情形图1中的顶点均可经过l-1长途径到达C1, 根据情形1.2.1, 可以得到综合以上三种情形, 即任取vi,vj∈V(D), vi,vj在D中经过长途径到达的公共点个数至少有2个, 根据m-competition指数的定义, 因此另一方面证明取点vn-l+2和点由图1可知因此综上,情形2: m≥1且m为奇数时, 一方面证明图1中所有顶点均可经过l-1长途径到达其中一个s圈, 任意一个s圈上的顶点集{v1,v2,…,vn-l+1}记为V1(特殊地，l=1时, V(D)=V1), 则对于任意vi,vj∈V(D), 在D中总有和而在本原有向图Ds中, V1中的点均为环点且顶点集{v1,v1+s,v2,v2+s,…,vs-1,vn,v1}形成一个n圈, 所以即任取两点vi,vj∈V(D), vi,vj在D中经过长途径到达的公共点个数至少为m. 根据m-competition指数的定义，因此另一方面,证明当m=1+4k时, 取特殊点vn-l+2和由图1可知当m=3+4k时, 取点vn-l+2和由图1可知所以综上,情形3 m=2+4k,4+4k且时, 一方面要证明图1中所有顶点均可经过l-1长途径到达任意一个s圈, 任意一个s圈上的顶点集{v1,v2,…,vn-l+1}记为V1(特殊地，l=1时, V(D)=V1), 则对于任意vi,vj∈V(D), 在D中总有和从而也有和而在本原有向图Ds中, V1中的点均为环点且顶点集{v1,v1+s,v2,v2+s,…,vs-1,vn,v1}形成一个n 圈, 所以即任取两点vi,vj∈V(D), vi,vj在D中经过长途径到达的公共点个数至少为m. 根据m-competition指数的定义, 因此另一方面, 证明取点vn-l+2和点由图1可知,即点vn-l+2和点在D中经过长途径到达的公共点个数为m-1,所以综上,综合上述三种情形,定理得证.【相关文献】[1] Akelbek M, Kirkland S. Coefficients of ergodicity and the scrambling index [J]. Linear Algebr-a and its Applications,2009,430(4):1111～1130.[2] Kim H K. Generalized competition index of a primitive digraph [J].Linear Algebra and its Applications,2010, 433 (1):72～79.[3] Akelbek M, Kirkland S. Primitive digraphs with the largest scrambling index [J].Linear Algebra and its Applications,2009, 430:1099～1110.[4] Chen S X, Liu B L. The scrambling index of symmetric primitive matrices[J].Linear Algebra and its Applications,2010,433(6):1110～1126.[5] Yubin Gao, Yanling Shao. The scrambling indeces of primitive digraphs with exactly two cycles [J].Ars Combinatoria,2013,108:505～513.[6] Shao Y L, Gao Y B.The m-competition indices of symmetric primitive digraphs with loop[J].Ars Combination, 2013, 108:217～223.[7] Kim H K, Pank S G. A bound of generalized competition index of a primitive digraph [J]. Linear Algebra and its Applications,2012, 436(1):86～98.。