一個本原有向圖的scrambling指數和廣義scrambling指數

樊 瑞，高玉斌

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

1 預備知識

近年來，scrambling指數和廣義scrambling指數是本原有向圖的一個新興研究分支.scrambling指數的研究是基于矩陣(或有向圖)的本原性特征，它在經濟學、生物學、化學、計算機科學等眾多學科中都具有廣泛的應用和重要的研究意義.2009年，Mahmud Akelbek和Steve Kirkland在文獻[1]中給出了有關本原有向圖scrambling指數的定義，并且討論了一類最小圈長為s的n階本原有向圖的指數的上界.同年，兩位作者又在文獻[2]中對達到scrambling指數的上界K(n，s)的圖進行了刻畫，求得了所有達到上界的本原有向圖.2010年，陳佘喜和柳伯濂在文獻[3]中研究了對稱圖scrambling指數的指數集、上界和極圖.隨后，柳伯濂和黃宇飛在文獻[4]中研究了含d個環的本原圖，極小強連通圖，幾乎可分解圖以及極小對稱圖等本原圖的scrambling指數，之后，兩位作者又在文獻[5]中給出了廣義scrambling指數的定義，并且研究了幾大類圖的廣義scrambling指數.

定義1.1[1]設D是n階本原有向圖，若存在正整數k，對于D中任意頂點vi和vj，都存在點ω∈V(D)，使得從vi和vj到ω都有k長途徑，滿足上述條件的最小正整數k稱為本原有向圖D的scrambling指數，記作k(D).

定義1.2[5]設D為n階本原有向圖，λ，μ∈Z，1≤λ，μ≤n.對于集合+X?V(D)定義(D)為最小的正整數l，使得存在μ個頂點ω1，ω2，…，ωμ∈V(D)，對任意的x∈X，都有，則

分別稱為本原有向圖D的λ重下μ－scrambling指數和λ重上μscrambling指數.特別地，當μ=1時，h(D，λ)=h(D，λ，1)，k(D，λ)=k(D，λ，1)，kX(D)=(D).

定義1.3[5]設D為n階本原有向圖，l為非負整數，當X?V(D)，且X≠?時，(X)表示從集合X中的點出發，經過l長途徑所能到達的點的集合.特別地，當l=0時(X)=X.

圖1 本原有向圖

2 主要結果

本文主要研究一個本原有向圖D(圖1)的scrambling指數和廣義scrambling指數，其中含有一個n(n≥7且n=2s－1)圈和兩個s圈.

定理2.1 設D是n(n≥7且n=2s－1)階本原有向圖(圖1)，則有

證明 因為D含有一個n(n≥7且n=2s－1)圈和兩個s圈，由本原有向圖scrambling指數的定義可知，下面只需證明對于任意頂點u，v∈V(D)，都有({u})∩({v})≠?成立，并且存在頂點 vi，vj∈V(D)，使得({vi})∩({vj－1})≠?.

由上可知，k(D)=l.

由上可知，k(D)=l.

定理2.2 設D是n(n≥7且n=2s－1)階本原有向圖(圖1)，則

一方面，存在頂點v2∈V(DT)，使得

所以，對于任意頂點 vi∈V(DT)(i=1，2，…，2s－1)，都有＜λ成立.

定理2.3 設D是n(n≥7且n=2s－1)階本原有向圖(圖1)，則

證明 設u1，u2，…，um(1≤m≤s)是本原有向圖D(圖1)中s圈上的任意m個不相同的點，并且，記長為s 的圈為Cs.首先證明 k{u1，u2，…，um}(D)≤s.考慮有向圖 D(s)，顯然 u1，u2，…，um是有向圖 D(s)上的環點，故因此，，其中 i=1，2，…，m.

(D(s))，使得i=1，2，…，m.也就是說，圖D中存在一個頂點 w∈V(D)，使得i=1，2，…，m.由此可知，k{u1，u2，…，um}(D)≤s

另外，對于任意λ個頂點vi∈V(D)，存在頂點wi∈V(Cs)，使得如果 λ ≤s，則|{w1，w2，…，wλ}|≤λ ;如果 λ ＞ s，則|{w1，w2，…，wλ}|≤s.可推出

[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]Chen S，Liu B.The scrambling index of symmetric primitive matrices[J].Linear Algebra and its Applications，2010，433:1110－1126.

[4]Liu B，Huang Y.The scrambling index of primitive digraphs[J].Computers and Mathematics with Applications，2010，60:706－721.

[5]Huang Y，Liu B.Generalized scrambling indices of a primitive digraph[J].Linear Algebra and its Applications，2010，433:1798－1808.