一个含4个圈的本原有向图的scrambling指数及广义scrambling指数

申佳，高玉斌

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

一个含4个圈的本原有向图的scrambling指数及广义scrambling指数

申佳，高玉斌

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

通过分析图中每一点通过t长途径所到达顶点的集合及顶点的个数,并且结合图论及组合数学的知识,得到一个含有两个s圈和两个s-1圈的本原有向图的scrambling指数以及广义scrambling指数.

本原有向图;途径；scrambling指数;广义scrambling指数

0 引 言

目前, 对本原有向图的本原指数的研究已扩展到对本原有向图scrambling指数的研究, 并且取得了许多成果. 本原有向图的scrambling指数及广义scrambling指数是一个新兴研究分支, 也是近n年来在组合数学中较为活跃的一个研究方向, 在计算机科学中具有广泛的实际应用背景.

文献[2]中,M.Akelbek和S.Kirkland从随机矩阵的第二大特征值入手,首次提出了scrambling指数的定义,进而在文献[3]中详细刻画了一般本原矩阵类的scrambling指数的上确界.而文献[4]中,M.Akelbek等使用布尔秩获得了伴随有向图的围长为s的n阶本原有向图的scrambling指数的上界.文献[5]中，柳柏濂和黄宇飞又给出了本原有向图的scrambling指数的一些新上界.同时,文献[6]中陈佘喜等研究了对称本原有向图的scrambling指数问题. 高玉斌、邵燕灵教授在文献[7]中得出了一类恰含一个p长圈和一个s长圈的n阶本原有向图的scrambling指数的上界并且上界可达，文献[8]中黄宇飞等以非记忆通讯系统为背景,对scrambling指数进行了推广,引入了广义scrambling指数的概念.文献[9]中,Hwa Kyung Kim研究了本原有向图的scrambling的指数集问题.

1 预备知识

2 主要结果及证明

图1 本原有向图D

另一方面，由于

另一方面,由于

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

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

[1]BrualdiRA,RyserHJ.CombinatorialMatrixTheory[M].CambridgeUniversityPress,1991.

[2]AkelbekM,KirklandS.Coefficientsofergodicityandscramblingindex[J].LinearAlgebraanditsApplications,2009, 430:1111-1130.

[3]AkelbekM,KirklandS.Primitivedigraphswiththelargestscramblingindex[J].LinearAlgebraanditsApplications,2009, 430:1099-1110.

[4]AkelbekM,FitalS,ShenJ.AboundonthescramblingindexofaprimitivematrixusingBooleanrank[J].Line-rAlgebraanditsApplications,2009, 431:1923-1931.

[5]LiuB,HuangY.Thescramblingindexofprimitivedigraphs[J].ComputersandMathematicswithApplicatio-ns,2010, 60:706-721.

[6]ChenS,LiuB.Thescramblingindexofsymmetricprimitivematrices[J].LinearAlgebraanditsApplications,2010, 433:1110-1126.

[7]YubinGao,YanlingShao.Thescramblingindecesofprimitivedigraphswithexactlytwocycles[J].ArsCombinatoria,2013, 108: 505-513.

[8]HuangY,LiuB.Generalizedscramblingindicesofaprimitivedigraphs[J].LinearAlgebraanditsApplications,2010, 433:1798-1808.

[9]HwaKK.Scramblingindexsetofprimitivedigraphs[J].LinearAlgebraanditsApplications,2013,439:1886-1893.

[责任编辑：王军]

The scrambling index and generalized scrambling indices of a primitive digraph with 4 cycles

SHEN Jia,GAO Yubin

(Department of Mathematics, North University of China, Taiyuan 030051, China)

Through analyses the vertex set of each vertex in digraph can be reached by a walk of lengtht,and combining with graph theory and combinational theory, we get the scrambling index and generalized scrambling indices of the primitive digraph with twos-cycles and two(s-1)-cycles.

primitive digraph;length;scrambling index;generalize scrambling index

2015-01-06

国家自然科学基金资助项目(NO.11071227);山西省回国留学人员科研资助项目(2012-070)

申佳(1991-)，女, 山西长治人, 中北大学硕士研究生, 主要从事组合数学研究.

高玉斌(1962-)，男, 山西忻州人, 中北大学理学院教授，博士生导师,主要从事组合数学的研究.

O

A

1672-3600(2015)06-0016-05