一類本原有向圖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-)，女，河北石家莊人，碩士研究生，主要從事組合數學方面的研究.