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

申佳,高玉斌

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

近几年来,对本原有向图本原指数的研究已扩展到对本原有向图scramling指数和m-competition指数的研究,并取得了许多成果。2009年,Akelbek和Kirkland[1]首次提出了本原图的scrambling指数的概念,2010年,黄宇飞等[2]以非记忆通讯系统为背景,对 scrambling指数进行了推广,引入了广义scrambling指数的概念。2010年,Hwa Kyung Kim[3]提出了本原图的m-competition指数这一概念。文献[4-8]研究了对称含环本原图的m-competition指数问题。本文研究结合广义 competition指数和广义scrambling指数的定义,对本原图中任一点经过k长途径所到达点的集合进行分析,研究一类特殊的本原有向图。

1 预备知识

设有向图D,若存在一个正整数l,使得D中任意 2个顶点 x,y(可相同),在D中都存在从x到y的l长途径,则称D是本原有向图,其中最小的正整数l称为D的本原指数,记为exp(D)。D的本原有向图的充分必要条件是D强连通,且D的所有圈长的最大公因子为1[9]。用表示从x到y有l长的途径。定义 Dl为一个本原有向图,其中当且仅当D中有

定义1[2]本原有向图D的scrambling指数是最小的正整数k,对任意一对顶点u和v,都存在w∈V(D),使得从u和v到w都有k长途径,这样的k称为本原有向图D的scrambling指数,记为k(D)。

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

定义3[4]设D是n阶本原有向图,1≤m≤n,对于任意的顶点 u,v ∈ V(D),存在正整数m,在D中总能找到m个点,使得 u,v到这m个点都存在k长途径(这m个点与u和v有关系),k的最小值称为D的m-competition指数,记作 km(D)。m-competition指数也称为广义competition指数。如果上述顶点 u,v ∈ V(D)已给定,则满足条件的最小的k称为点x,y在D中的局部广义competition指数,记为

文中用文献[10]中的记号 N+(Dk:x)表示在D中点x经过k长途径所到达点的集合,用表示集合中点的个数。

2 主要结论

本文研究一类含有 2个 1s-圈和s个s圈的n阶本原有向图1D和2D(图1、图2)的m-competition指数以及广义scrambling指数。

图1 1D图

图2 2D图

定理 1 设 n(n≥7)阶本原图 D1(D2)如图1(图2)所示,其中 n=2 s-1,4≤s≤n-1,则对于正整数 m(1≤m≤n),有:

情形2 1≤m≤s 且s+ m 为偶数。

一方面,对任意 x,y ∈ V(D1),存在使得在D1中有且在本原有向图(图4)中,顶点均为环点且成一个s圈,记为2C。

图3 图

图4 图

证明 km(D1)和 km(D2)的证明过程类似,仅证明(1)式。

情形3 m≥s+2且s+m为偶数。

另一方面,取特殊点 vn,vn-1,在图中,易知 vn,vn-1经过 s-1 长途径所到达的公共点个数为s(＜m),所以因此,

情形4 m≥s+1且s+m为奇数。

类似地,可得到km(D2)。定理得证。

推论1 根据定理1,当1m=时,可得本原有向图1D和2D的scrambling指数:

定理2 设n(n≥7)阶本原图D1(D2)如图1(图2)所示,其中

证明 仅证明(3)式。

定理3 设n(n≥7)阶本原图D1(D2)如图1(图2)所示,其中 n=2s-1,4≤s≤n-1,则对于正整数m(1≤m≤n),有

证明 设Cs-1是本原有向图D1(图1)上长为s-1圈,u1,u2,…,uλ(1≤λ≤s-1)是D1中s-1圈上的任意λ个不同的点,则在有向图是环点。于是必存在一个顶点 w ∈ V(D)使得成立。因此,由kX(D)的定义可知,

另外,对于任意λ个顶点vi∈V(D1),存在顶点使得vi到wi有 s-1长途径(i=1,2,…,λ)。于是当λ≤s-1时当λ＞s时,因此可以得到

[1]Akelbek M,Kirkland S.Coefficients of ergodicity and the scrambling index [J].Linear Algebra and its Applications,2009,430(4):1 111-1 130.

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

[3]Kim H K.Generalized competition index of a primitive digraph [J].Linear Algebra and its Applications,2010,433(1):72-79.

[4]Shao Y L,Gao Y B.The m-competition indices of symmetric primitive digraphs with loop [J].Ars Combination,2013,108:217-223.

[5]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.

[6]Akelbek M,Kirkland S.Primitive digraphs with the largest scrambling index [J].Linear Algebra and its Applications,2009,430:1 099-1 110.

[7]Gao Y,Shao Y.The scrambling indices of primitive digraphs with exactly two cycles [J].Ars Combination,2013,108:505-513.

[8]Hwa K K.Scrambling index set of primitive digraphs [J].Linear Algebra and its Applications,2013,439:1 886-1 893.

[9]Brualdi R A,Ryser H J.Combinatorial Matrix Theory [M].Cambridge:Cambridge University Press,1991.

[10]Kim H K,Lee S H.Generalized competition indices of symmetric primitive digraphs [J].Discrete Applied Mathematics,2012,160(10-11):1 583-1 590.