一类本原有向图D的scrambling指数及广义scrambling指数

甄　琳，雷英杰

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

一类本原有向图D的scrambling指数及广义scrambling指数

甄琳，雷英杰

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

对含有3个圈的n阶本原有向图D的scrambling指数进行研究，通过分析每一点经过t长途径可到达的点的集合，并根据本原有向图的scrambling指数和广义scrambling指数的定义，分别得出该图的scrambling指数和λ重下μ-scrambling指数的精确值，也得到了λ重上μ-scrambling指数的上界.

本原有向图;scrambling指数;广义scrambling指数;集合

1　引言及预备知识

设D=(V，E)是由顶点集V=V(D)和弧集E=E(D)构成的有向图(可以有环，但不能有重弧).一个有向图D称为本原有向图，如果对于∀u，v∈V(D)，都存在从u到v的t长途径.有向图D是本原的充分必要条件是D是强连通的，并且D中所有圈长的最大公因子为1.定义DT是D的转置，V(DT)=V(D)，对于任意顶点 vi，vj∈ V(D) ，弧 (vi，vj) ∈ E(D) ，当且仅当弧(vj，vi)∈ E(DT).定义 Dr是有向图，其中V(Dr)=V(D)，(vi，vj)∈E(Dr)，在D中当且仅当vi到vj有r长途径.R({v})是指从顶点v经过l长途径所能到达的点的集合，则R({v})是指D中经过l长途径到达顶点v的点的集合.

2009年，Mahmud Akelbek和 Steve Kirkland在文献［1］中首次提出本原有向图scrambling指数的定义，在文献［2］中给出伴随有向图的围长为s的n阶本原矩阵的scrambling指数的上确界.2010年，柳柏濂和黄宇飞在文献［3］中以非记忆通讯系统为背景，将scrambling指数进行推广，引入了广义scrambling指数.

定义1［1］设D是n阶本原有向图，满足以下条件的最小正整数k称为n阶本原有向图D的scrambling指数，即对D中任意一对顶点u和v，总存在w∈V(D)，使得从u和v到w都有k长途径，记作k(D).

对于两个不同的顶点u和v，

定义2［3］设D是n阶本原有向图，λ和μ是整数且1≤λ，μ≤n，对于集合X⊆V(D)，定义k(μ)X(D)为最小的正整数m，使得存在μ个顶点 w1，w2，…，wμ∈ V(D) ，对于任意的顶点 x ∈X，都有从x到wi(i=1，2，…，μ)的 m 长途径，则

2　主要结论

图1　本原有向图D

［1］Akelbek M，Kirkland S.Coefficients of ergodicity and the scrambling index［J］.Linear Algebra and its Applications，2009，430:1111-1130.

［2］Akelbek M，Kirkland S.Primitive digraphs with the largest scrambling index［J］.Linear Algebra and its Applications，2009，430:1099-1110.

［3］Huang Y F，Liu B L.Generalized scrambling indices ofa primitive digraph［J］.Linear Algebra and its Applications，2010，433:1798-1808.

［4］Liu B L，Huang Y F.The scrambling index of primitive digraphs［J］.ComputersandMathematicswith Applications，2010，60:706-721.

［5］Chen SX，Liu B L.The scrambling index of symmetric primitive matrices［J］.Linear Algebra and its Applications，2010，433:1110-1126.

(责任编辑穆刚)

The scrambling index and generalized scrambling indices of one class prim itive digraphs

ZHEN Lin，LEIYingjie

(Department of Mathematics，North University of China，Taiyuan Shanxi 030051，China)

The scrambling index of a primitive digraph with three cycleswas studied.By analyzing the set of points that each point in digraph got to by directed walks of length t，and according to the definition of scrambling index and generalized scrambling indices，finally the exact value of scrambling index and theλth lowerμ -scrambling indices are given，also the upper bound of theλth upperμ -scrambling indices was got.

primitive digraph;scrambling index;generalized scrambling indices;set

O157.5

A

1673-8004(2014)05-0017-03

2014-04-14

国家自然科学基金项目(11071227).

甄琳(1989-)，女，河北石家庄人，硕士研究生，主要从事组合数学方面的研究.