一類特殊本原有向圖的廣義的scrambling指數(shù)

孫琳莉，雷英杰

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

如果存在正整數(shù)k，使得對于D中任意頂點u，v在D中都存在一點ω，都有從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為含有一個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)．

1 主要結(jié)論

引理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．