一個含4個圈的本原有向圖的scrambling指數(shù)及廣義scrambling指數(shù)

申佳，高玉斌

(中北大學(xué) 數(shù)學(xué)系，山西 太原 030051)

一個含4個圈的本原有向圖的scrambling指數(shù)及廣義scrambling指數(shù)

申佳，高玉斌

(中北大學(xué) 數(shù)學(xué)系，山西 太原 030051)

通過分析圖中每一點通過t長途徑所到達(dá)頂點的集合及頂點的個數(shù),并且結(jié)合圖論及組合數(shù)學(xué)的知識,得到一個含有兩個s圈和兩個s-1圈的本原有向圖的scrambling指數(shù)以及廣義scrambling指數(shù).

本原有向圖;途徑；scrambling指數(shù);廣義scrambling指數(shù)

0 引 言

目前, 對本原有向圖的本原指數(shù)的研究已擴展到對本原有向圖scrambling指數(shù)的研究, 并且取得了許多成果. 本原有向圖的scrambling指數(shù)及廣義scrambling指數(shù)是一個新興研究分支, 也是近n年來在組合數(shù)學(xué)中較為活躍的一個研究方向, 在計算機科學(xué)中具有廣泛的實際應(yīng)用背景.

文獻(xiàn)[2]中,M.Akelbek和S.Kirkland從隨機矩陣的第二大特征值入手,首次提出了scrambling指數(shù)的定義,進而在文獻(xiàn)[3]中詳細(xì)刻畫了一般本原矩陣類的scrambling指數(shù)的上確界.而文獻(xiàn)[4]中,M.Akelbek等使用布爾秩獲得了伴隨有向圖的圍長為s的n階本原有向圖的scrambling指數(shù)的上界.文獻(xiàn)[5]中，柳柏濂和黃宇飛又給出了本原有向圖的scrambling指數(shù)的一些新上界.同時,文獻(xiàn)[6]中陳佘喜等研究了對稱本原有向圖的scrambling指數(shù)問題. 高玉斌、邵燕靈教授在文獻(xiàn)[7]中得出了一類恰含一個p長圈和一個s長圈的n階本原有向圖的scrambling指數(shù)的上界并且上界可達(dá)，文獻(xiàn)[8]中黃宇飛等以非記憶通訊系統(tǒng)為背景,對scrambling指數(shù)進行了推廣,引入了廣義scrambling指數(shù)的概念.文獻(xiàn)[9]中,Hwa Kyung Kim研究了本原有向圖的scrambling的指數(shù)集問題.

1 預(yù)備知識

2 主要結(jié)果及證明

圖1 本原有向圖D

另一方面，由于

另一方面,由于

定理3 設(shè)n階本原有向圖D(如圖1所示),則有

定理 4 設(shè)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.

[責(zé)任編輯：王軍]

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

國家自然科學(xué)基金資助項目(NO.11071227);山西省回國留學(xué)人員科研資助項目(2012-070)

申佳(1991-)，女, 山西長治人, 中北大學(xué)碩士研究生, 主要從事組合數(shù)學(xué)研究.

高玉斌(1962-)，男, 山西忻州人, 中北大學(xué)理學(xué)院教授，博士生導(dǎo)師,主要從事組合數(shù)學(xué)的研究.

O

A

1672-3600(2015)06-0016-05