張潔敏，高玉斌

?

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

張潔敏，*高玉斌

（中北大學理學院，山西，太原 030051）

對兩類本原有向圖進行研究。結合本原有向圖的特點，對圖中的每一點經(jīng)過長途徑所到達的點集合進行分析，根據(jù)廣義scrambling指數(shù)定義，得到了這兩類本原有向圖的廣義scrambling指數(shù)。

本原有向圖；點；途徑；廣義scrambling指數(shù)

2009年，Akelbek M 和Kirkland S根據(jù)隨機矩陣的第二大特征值，在文獻[1]中提出了本原有向圖的scrambling指數(shù)定義，并在文獻[2]中給出了圍長為s的本原有向圖scrambling指數(shù)的上確界，還解決了一般本原有向圖的scrambling指數(shù)上確界。Akelbek M，F(xiàn)ital S等在文獻[3]中利用布爾秩求出本原有向圖的scrambling指數(shù)的上界。文獻[4]研究了一類特殊本原有向圖的scrambling指數(shù)。2010年，黃宇飛，柳柏濂在文獻[5]中將scrambling指數(shù)推廣到廣義scrambling指數(shù)，給出了本原有向圖的廣義scrambling指數(shù)定義，并給出了三類本原有向圖的廣義scrambling指數(shù)的確界與極圖。文獻[6] 研究了2個特殊本原有向圖的scrambling指數(shù)與廣義scrambling指數(shù)。

1 預備知識

設為階有向圖（可以有環(huán)，但不能有重?。?，若存在正整數(shù)，使得對任意一對從到都有長為的途徑（記），則稱為本原有向圖，并稱滿足條件的最小正整數(shù)為本原有向圖的本原指數(shù)，記為。有向圖是本原有向圖等價于有向圖為強連通圖，且中所有圈長的最大公因子為1[7]。

對有向圖D有如下定義：(D)=()，對有向圖D有如下定義：(D)=()

定義1[1]設為階本原有向圖，若存在正整數(shù)對任意一對總存在一點使得在中有則稱滿足條件的最小正整數(shù)為的scrambling指數(shù)，記為。

定義2[5]設為階本原有向圖，正整數(shù)對于集合用來表示最小的正整數(shù)使得存在個頂點對于在中都有，則將

分別稱為本原有向圖的重下–scrambling指數(shù)和重上–scrambling指數(shù)。當=1時，記稱為本原有向圖的廣義scrambling指數(shù)。

引理1[5]設為階本原有向圖，有，。

2 主要結果

定理1 令1為如圖1表示的階本原有向圖，則對正整數(shù)有

。

；

根據(jù)引理1可知

。

圖2 n階本原有向圖

；

。

參考文獻：

[1] Akelbek M, Kirkland S. Coefficients of ergodicity and the scrambling index [J].Linear Algebra and its Applications, 2009,430(4):1111-1130.

[2] Akelbek M, Kirkland S. Primitive digraphs with the largest scrambling index [J]. LinearAlgebra and its Applications, 2009, 430(4):1099-1110.

[3] Akelbek M, Fital S, Shen J. A bound on the scrambling index of a primitive matrix using Boolean rank [J]. Linear Algebra and its Applications, 2009,431(10):1923-1931.

[5] Huang Yufei, Liu Bolian. Generalized scrambling indices of a primitive digraph [J]. Linear Algebra and its Applications, 2010, 433(11):1798-1808.

[6] 代愛鳳,邵燕靈.2個特殊本原有向圖的scrambling指數(shù)與廣義scrambling指數(shù)[J].天津師范大學學報:自然科學版, 2012, 32(3):9-12.

[7] Brualdi R A, Ryser H J. Combinatorial Matrix Theory [M]. Cambridge:Cambridge University Press, 1991.

GENERALIZED SCRAMBLING INDICES OF TWO CLASSES OF PRIMITIVE DIGRAPH

ZHANG Jie-min,*GAO Yu-bin

（School of Science, North University of China, Taiyuan,Shanxi 030051, China）

Two classes of primitive digraph are discussed. Combing with the characteristics of the digraph, we analyze the sets formed by the vertexes, which are arrived by every vertex passing a walk of lengthin the digraph. According to the definitions of generalized scrambling indices, we obtain the generalized scrambling indices of two classes of primitive digraph.

primitive digraph; vertex; walk; generalized scrambling indices

1674-8085(2015)01-0030-04

O157.5

A

10.3969/j.issn.1674-8085.2015.01.006

2014-09-24；修改日期：2014-11-20

山西省回國留學人員科研項目（2012-070）

張潔敏(1990-)，女，河南焦作人，碩士生，主要從事組合數(shù)學的研究(E-mail:1367356120@qq.com);

*高玉斌(1962-)，男，山東保德人，教授，博士生導師，主要從事組合數(shù)學的研究(E-mail:ybgao@nuc.edu.cn).