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

張潔敏，高玉斌

?

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

張潔敏，*高玉斌

（中北大學(xué)理學(xué)院，山西，太原 030051）

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

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

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

1 預(yù)備知識(shí)

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

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

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

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

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

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

2 主要結(jié)果

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

。

；

根據(jù)引理1可知

。

圖2 n階本原有向圖

；

。

參考文獻(xià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個(gè)特殊本原有向圖的scrambling指數(shù)與廣義scrambling指數(shù)[J].天津師范大學(xué)學(xué)報(bào):自然科學(xué)版, 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

山西省回國(guó)留學(xué)人員科研項(xiàng)目（2012-070）

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

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