一個特殊本原有向圖的scrambling指數及廣義scrambling指數

張佩, 王卓宇, 高玉斌

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

一個特殊本原有向圖的scrambling指數及廣義scrambling指數

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

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

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

本原有向圖; scrambling指數; 廣義scrambling指數;途徑

1 預備知識

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

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

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

設DT是D的轉置,V(DT)=V(D),對于任意的頂點vi,vj∈V(D),弧(vi,vj)∈E(D),當且僅當弧(vj,vi)∈E(DT).根據h(D,λ)的定義,我們有以下三個結論:

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

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

2 主要結果

圖1 本原有向圖D

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

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

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

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

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

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

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

定理 4 設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.

【責任編輯：王軍】

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

山西省回國留學人員科研資助項目(12-070)

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

O157.5

A

1672-3600(2015)03-0033-04