一個n階本原有向圖的m-competition指數

劉彩鋒，高玉斌

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

一個n階本原有向圖的m-competition指數

劉彩鋒，高玉斌

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

文中討論了一個含有一個n-2圈和一個n-3圈的n階本原有向圖D.由D的結構得到本原圖Dn-2和Dn-3, 然后分別對本原圖D, Dn-2和Dn-3中任一點經過k長途徑所到達的頂點的集合以及頂點的個數進行分析, 再結合m-competition指數的定義, 得到這個本原圖的m-competition指數.

有向圖; 本原圖; m-competition指數

1 預備知識

近年來, 本原有向圖的scrambling指數和m-competition指數是學者們的一個新興研究分支.2009年,Akelbek和Kirkland在文獻[2]中提出了本原有向圖的scrambling指數的概念.2010年, Hwa Kyung Kima將本原圖的本原指數和scrambling指數推廣到m-competition指數(也叫廣義competition指數), 并在文獻[3]中給出m-competition指數的定義, 隨后, 他找到了本原矩陣的m-competition指數的上界, 同時確定了最小圈長為s的本原圖的m-competition指數的上界, 而文中討論了一個特殊本原有向圖的m-competition指數.

定義1[2]設D為n階有向圖, 如果存在正整數m, 使得對于D中任意兩點x,y, 從x到y都有m長的途徑, 則稱D為本原有向圖, 或稱本原圖.

有向圖D是本原圖的充要條件是D為強連通圖且D中所有圈長的最大公因子為1[1].如果D為本原圖, 則Dl也為本原圖.D為強連通圖是指D為有向圖且任意頂點u,v∈V(D), 既存在u到v的途徑, 又存在v到u的途徑[1].

文中符號N+(Dk:x)表示點x在D中經過k長途徑所到達點的集合, |N+(Dk:x)|表示集合中頂點的個數.N+(Dk:x,y)表示頂點x和y在D中經過k長途徑所到達公共點的集合, 即N+(Dk:x,y)=N+(Dk:x)∩N+(Dk:y).

設D為一個本原圖, C為D中的一個圈, 則用l(C)來表示C的圈長.文中本原有向圖中的頂點上的小圓圈表示一個環, 即該頂點是一個環點, 環的方向可以任意, 既可以順時針也可以逆時針.

2 主要定理及證明

定理設n階(n≥12)本原圖D如圖1所示，D中含有一個n-2圈和一個n-3圈,

則對于正整數m(1≤m≤n), D的m-competition指數為

證明 情形1 1≤m≤n-5且n+m為奇數.

子情形1 對任意x,y∈V(D)且x,y≠vn-3和vn-4時,存在vi,vj∈V(D)(4≤i,j≤n-2),

(2)

子情形3 當x,y等于vn-3和vn-4時, 不妨設x=vn-3,y=vn-4時, 由上(1)(2)式可得

情形2 1≤m≤n-4且n+m為偶數.

子情形1 對任意x,y∈V(D)且x,y≠v1,vn-3,vn-2, 存在vi,vj∈V(D), 其中

子情形2 對任意x,y∈V(D)且x,y中有一個等于v1或vn-3或vn-2時, 不妨設x=v1,

在Dn-3中取特殊點v1和

情形3 m=n-3.

在Dn-2中, N+((Dn-2)n-4:v1)=V(D){vn-2},N+((Dn-2)n-4:v2)=V(D){v1,vn-1},

N+((Dn-2)n-4:v3)=V(D){v2,vn}, N+((Dn-2)n-4:v4)=V(D){v3},

N+((Dn-2)n-4:vj)=V(D)(5≤j≤n-2), N+((Dn-2)n-4:vn-1)=V(D){v1,vn-1},

N+((Dn-2)n-4:vn)=V(D){v2,vn}.

即在D中,N+(D2+(n-2)(n-4):v1)=V(D){v2,vn},N+(D2+(n-2)(n-4):v2)=V(D){v3},

N+(D2+(n-2)(n-4):vi)=V(D)(3≤i≤n-4),

N+(D2+(n-2)(n-4):vn-3)=V(D){vn-2}∪V(D){v1,vn-1}=V(D),

N+(D2+(n-2)(n-4):vn-2)=V(D){v1,vn-1}∪V(D){v2,vn}=V(D),

N+(D2+(n-2)(n-4):vn-1)=V(D){v3}, N+(D2+(n-2)(n-4):vn)=V(D).

則任意x,y∈V(D), 在D中經過2+(n-2)(n-4)長途徑至少含有n-3個公共點, 從而kn-3(D:x,y)≤2+(n-2)(n-4).

N+(D1+(n-2)(n-4):v1,v2)=V(D){v1,vn-1}∩V(D){v2,vn}=V(D){v1,v2,vn-1,vn},

即在D中v1和v2經過1+(n-2)(n-4)長途徑所含公共點個數小于n-3, 從而

kn-3(D)>1+(n-2)(n-4). 綜上所述kn-3(D)=2+(n-2)(n-4).

情形4 m=n-2.

kn-2(D:x,y)≤3+(n-2)(n-4).

下面證kn-2(D)>2+(n-2)(n-4).

取特殊點

V(D){v3}, 所以N+(D2+(n-2)(n-4):v1,v2)=V(D){v2,vn}∩V(D){v3}=V(D){v2,v3,vn}, 即在D中v1和v2經過2+(n-2)(n-4)長途徑所到達的公共點的個數小于n-2, 從而kn-2(D)>2+(n-2)(n-4). 綜上所述

kn-2(D)=3+(n-2)(n-4).

情形5 m=n-1.

在Dn-3中,N+((Dn-3)n-3:v1)=V(D){v1,vn-1},N+((Dn-3)n-3:v2)=V(D){v2,vn},

N+((Dn-3)n-3:v3)=V(D){v3}=N+((Dn-3)n-3:vn),

N+((Dn-3)n-3:vj)=V(D)(4≤j≤n-2), N+((Dn-3)n-3:vn-1)=V(D){v2,vn}.

即在D中, N+(D2+(n-3)(n-3):v1)=V(D){v3},

N+(D2+(n-3)(n-3):vi)=V(D)(2≤i≤n-4),

N+(D2+(n-3)(n-3):vn-3)=V(D){v1,vn-1}∪V(D){v2,vn}=V(D),

N+(D2+(n-3)(n-3):vn-2)=V(D){v2,vn}∪V(D){v3}=V(D),

N+(D2+(n-3)(n-3):vn-1)=V(D)=N+(D2+(n-3)(n-3):vn).

則任意x,y∈V(D), 在D中經過2+(n-3)(n-3)長途徑至少含有n-1個公共點, 從而kn-1(D:x,y)≤2+(n-3)(n-3).

即在D中v1經過1+(n-3)(n-3)長途徑所到達的點的個數小于n-1, 從而

kn-1(D)>1+(n-3)(n-3). 綜上所述kn-1(D)=2+(n-3)(n-3).

情形6 m=n.

kn(D:x,y)≤3+(n-3)(n-3).

下面證kn(D)>2+(n-3)(n-3).

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

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

[3] Kim H K.Generalized competition index of a primitive digraph [J].Linear Algebra and its Applications,2010, 433 (1):72-79.

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

[5] Shao Y L, Gao Y B.The m-competition indices of symmetric primitive digraphs with loop[J].Ars Combination, 2013, 108:217-223.

[責任編輯：王軍]

The m-competition index of a primitive digraph of order n

LIU Caifeng,GAO Yubin

(Department of Mathematics, North University of China, Taiyuan 030051,China)

In this paper, a primitive digraph D of order n with one (n-1)-cycle and one (n-2)-cycle is considered.According to the structure of D, we draw up the primitive digraphsDn-2andDn-3.Then the sets and the numbers of vertexes, which are formed by each vertex passing a walk of length k in the primitive digraphs D, Dn-2and Dn-3are discussed respectively.In addition, based on the definition of m-competition index, we work out the m-competition index of the primitive digraph.

digraph; primitive digraph; m-competition index

2015-01-12

國家自然科學基金資助項目(11071227)；山西省回國留學人員科研資助項目(2012-070)

劉彩鋒(1988-)，女，山西呂梁人，中北大學碩士研究生，主要從事組合數學的研究.

高玉斌(1962-)，男，中北大學理學院教授，博士生導師，主要從事組合數學的研究.

O157.5

A

1672-3600-(2015)09-0001-06