甄　琳，雷英杰

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

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

甄琳，雷英杰

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

對(duì)含有3個(gè)圈的n階本原有向圖D的scrambling指數(shù)進(jìn)行研究，通過(guò)分析每一點(diǎn)經(jīng)過(guò)t長(zhǎng)途徑可到達(dá)的點(diǎn)的集合，并根據(jù)本原有向圖的scrambling指數(shù)和廣義scrambling指數(shù)的定義，分別得出該圖的scrambling指數(shù)和λ重下μ-scrambling指數(shù)的精確值，也得到了λ重上μ-scrambling指數(shù)的上界.

本原有向圖;scrambling指數(shù);廣義scrambling指數(shù);集合

1　引言及預(yù)備知識(shí)

設(shè)D=(V，E)是由頂點(diǎn)集V=V(D)和弧集E=E(D)構(gòu)成的有向圖(可以有環(huán)，但不能有重弧).一個(gè)有向圖D稱為本原有向圖，如果對(duì)于?u，v∈V(D)，都存在從u到v的t長(zhǎng)途徑.有向圖D是本原的充分必要條件是D是強(qiáng)連通的，并且D中所有圈長(zhǎng)的最大公因子為1.定義DT是D的轉(zhuǎn)置，V(DT)=V(D)，對(duì)于任意頂點(diǎn) vi，vj∈ V(D) ，弧 (vi，vj) ∈ E(D) ，當(dāng)且僅當(dāng)弧(vj，vi)∈ E(DT).定義 Dr是有向圖，其中V(Dr)=V(D)，(vi，vj)∈E(Dr)，在D中當(dāng)且僅當(dāng)vi到vj有r長(zhǎng)途徑.R({v})是指從頂點(diǎn)v經(jīng)過(guò)l長(zhǎng)途徑所能到達(dá)的點(diǎn)的集合，則R({v})是指D中經(jīng)過(guò)l長(zhǎng)途徑到達(dá)頂點(diǎn)v的點(diǎn)的集合.

2009年，Mahmud Akelbek和 Steve Kirkland在文獻(xiàn)［1］中首次提出本原有向圖scrambling指數(shù)的定義，在文獻(xiàn)［2］中給出伴隨有向圖的圍長(zhǎng)為s的n階本原矩陣的scrambling指數(shù)的上確界.2010年，柳柏濂和黃宇飛在文獻(xiàn)［3］中以非記憶通訊系統(tǒng)為背景，將scrambling指數(shù)進(jìn)行推廣，引入了廣義scrambling指數(shù).

定義1［1］設(shè)D是n階本原有向圖，滿足以下條件的最小正整數(shù)k稱為n階本原有向圖D的scrambling指數(shù)，即對(duì)D中任意一對(duì)頂點(diǎn)u和v，總存在w∈V(D)，使得從u和v到w都有k長(zhǎng)途徑，記作k(D).

對(duì)于兩個(gè)不同的頂點(diǎn)u和v，

定義2［3］設(shè)D是n階本原有向圖，λ和μ是整數(shù)且1≤λ，μ≤n，對(duì)于集合X?V(D)，定義k(μ)X(D)為最小的正整數(shù)m，使得存在μ個(gè)頂點(diǎn) w1，w2，…，wμ∈ V(D) ，對(duì)于任意的頂點(diǎn) x ∈X，都有從x到wi(i=1，2，…，μ)的 m 長(zhǎng)途徑，則

2　主要結(jié)論

圖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.

(責(zé)任編輯穆剛)

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

國(guó)家自然科學(xué)基金項(xiàng)目(11071227).

甄琳(1989-)，女，河北石家莊人，碩士研究生，主要從事組合數(shù)學(xué)方面的研究.