孫琳莉,雷英杰
(中北大學(xué)數(shù)學(xué)系,山西 太原 030051)
如果存在正整數(shù)k,使得對于D中任意頂點(diǎn)u,v在D中都存在一點(diǎn)ω,都有從u到ω,從v到ω都有長為k的路徑,則稱滿足上述條件的最小的正整數(shù)k稱為D的scrambling指數(shù),記為k(D).對于任意的u,v∈V(D),u,v的 scrambling 指數(shù)為
顯然有:
成立,則:
分別稱為D的第λ重下μ-scrambling指數(shù)和第λ重上μ-srambling指數(shù).
為方便起見,我們令
引理2[2]設(shè)D為含有一個(gè)Hamilton圈的n階本原有向圖,D中最小圈長為s,且1≤s≤n-1 ,如果 gcd(n,s)=1 ,則有:
k(D) ≤ K(n,s)=n-s+k(n,s) .
其中
定理 3[2]設(shè) D=Ds,n,gcd(n,s)=1 ,2≤ s≤ n-1,則有k(D)=K(n,s).
引理4 已知D是如圖1所示的本原有向圖,
則有
圖1 本原有向圖D
[1]Huang Yufei,Liu Bolian.Generalized scrambling indices of a primitive digraph[J].Linear Algebra Applications,2010(433):1798-1808.
[2]Akelbek M,Kirkland S.Coefficients of ergodicity and the scrambling index[J].Linear Algebra Applications,2009(430) :1111-1130.
[3]Chen Shexi,Liu Bolian.The scrambling index of symmetric primitive matrices[J].Linear Algebra Applications,2010(433):1110-1126.
[4]Akelbek M,Kirkland S.Primitive digraphs with the largest scrambling index[J].Linear Algebra Applications,2009(430):1099-1110.
[5]Liu Bolian,Huang Yufei.The scrambling index of primitive digraphs[J].Computers and Mathematics with Applications,2010(60):706-732.