一個(gè)特殊本原有向圖的scrambling指數(shù)及廣義scrambling指數(shù)

張佩, 王卓宇, 高玉斌

(1.中北大學(xué) 數(shù)學(xué)系, 山西 太原 030051;2.東華大學(xué) 理學(xué)院, 上海 201620)

一個(gè)特殊本原有向圖的scrambling指數(shù)及廣義scrambling指數(shù)

張佩1, 王卓宇2, 高玉斌1

(1.中北大學(xué) 數(shù)學(xué)系, 山西 太原 030051;2.東華大學(xué) 理學(xué)院, 上海 201620)

主要研究一個(gè)含有6個(gè)圈的n階本原有向圖,其中包含1個(gè)n-1圈,3個(gè)n-2圈和2個(gè)n-3圈.結(jié)合圖論與組合論的相關(guān)知識(shí),得出該圖的scrambling指數(shù)和廣義scrambling指數(shù).

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

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

定義 1[1]設(shè)有向圖D,若存在一個(gè)正整數(shù)l,使得D中的任意兩個(gè)頂點(diǎn)x,y(可以相同),在D中都存在從x到y(tǒng)的l長(zhǎng)途徑,則稱(chēng)D是本原有向圖,其中最小的正整數(shù)l稱(chēng)為D的本原指數(shù),記為exp(D).

引理 1[2]有向圖D是本原的充分必要條件是D為強(qiáng)連通,且D的所有圈長(zhǎng)的最大公因子為1.

定義 2[2]設(shè)D是n階本原有向圖,如果存在正整數(shù)k,對(duì)D中任意頂點(diǎn)u和v,都存在頂點(diǎn)w∈V(D),使得從u和v到w都有k長(zhǎng)途徑,則稱(chēng)滿(mǎn)足上述條件的最小正整數(shù)k為本原有向圖D的scrambling指數(shù),記為k(D).

設(shè)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).根據(jù)h(D,λ)的定義,我們有以下三個(gè)結(jié)論:

(3)h(D,1)=k(D,1)=1,h(D,n)=k(D,n).

本文主要研究一類(lèi)含6個(gè)圈的本原有向圖D(如圖1所示)的scrambling指數(shù)和廣義scrambling指數(shù).

2 主要結(jié)果

圖1 本原有向圖D

定理1 設(shè)D是如圖1所示的n(n≥7)階本原有向圖,若n≡1(mod2),則有:

證明 圖D中含有1個(gè)n-1圈,3個(gè)n-2圈和2個(gè)n-3圈.

定理 2 設(shè)D是如圖1所示的n(n≥7)階本原有向圖,若n≡0(mod2),則有:

證明 圖D中含有1個(gè)n-1圈,3個(gè)n-2圈和2個(gè)n-3圈.

定理3 設(shè)D是n階本原有向圖如圖1所示,則

當(dāng)λ=2,3時(shí),顯然h(D,λ)=1.下面證明λ≥4的情況:

綜上所述,h(D,λ)=t.定理得證.

定理 4 設(shè)D是n階本原有向圖(如圖1)所示,則有

[1] Brualdi R A,Ryse H J. Combinatorial Matrix Theory[M]. Cambridge University Press,1991.

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

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

[4] Huang Y, Liu B. Generalized scrambling indices of a primitive digraphs [J]. Linear Algebra and its Applications,2010, 433:1798-1808.

【責(zé)任編輯：王軍】

The scrambling index and generalized scrambling indices of a special primitive digraph

ZHANG Pei1，WANG Zhuoyu2,GAO Yubin1

(1.Department of Mathematics, North University of China, Taiyuan 030051, China;2.School of Science, Donghua University, Shanghai 201620, China)

A primitive digraph with five cycles are discussed. It contains one (n-1)-cycle, three (n-2)-cycles and two (n-3)-cycles. Combining with graph theory and combinational theory, the scrambling index and generalized scrambling indices of this primitive digraph are given.

primitive digraph; scrambling index; generalized scrambling indices;walk

2014-09-11

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

張佩(1989-),女,山西運(yùn)城市人,中北大學(xué)碩士研究生,主要從事圖論與組合數(shù)學(xué)的研究.

O157.5

A

1672-3600(2015)03-0033-04