一個(gè)n階本原有向圖的m-competition指數(shù)

劉彩鋒，高玉斌

(中北大學(xué) 數(shù)學(xué)系，山西 太原 030051)

一個(gè)n階本原有向圖的m-competition指數(shù)

劉彩鋒，高玉斌

(中北大學(xué) 數(shù)學(xué)系，山西 太原 030051)

文中討論了一個(gè)含有一個(gè)n-2圈和一個(gè)n-3圈的n階本原有向圖D.由D的結(jié)構(gòu)得到本原圖Dn-2和Dn-3, 然后分別對本原圖D, Dn-2和Dn-3中任一點(diǎn)經(jīng)過k長途徑所到達(dá)的頂點(diǎn)的集合以及頂點(diǎn)的個(gè)數(shù)進(jìn)行分析, 再結(jié)合m-competition指數(shù)的定義, 得到這個(gè)本原圖的m-competition指數(shù).

有向圖; 本原圖; m-competition指數(shù)

1 預(yù)備知識

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

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

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

文中符號N+(Dk:x)表示點(diǎn)x在D中經(jīng)過k長途徑所到達(dá)點(diǎn)的集合, |N+(Dk:x)|表示集合中頂點(diǎn)的個(gè)數(shù).N+(Dk:x,y)表示頂點(diǎn)x和y在D中經(jīng)過k長途徑所到達(dá)公共點(diǎn)的集合, 即N+(Dk:x,y)=N+(Dk:x)∩N+(Dk:y).

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

2 主要定理及證明

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

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

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

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

(2)

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

情形2 1≤m≤n-4且n+m為偶數(shù).

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

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

在Dn-3中取特殊點(diǎn)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中經(jīng)過2+(n-2)(n-4)長途徑至少含有n-3個(gè)公共點(diǎn), 從而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經(jīng)過1+(n-2)(n-4)長途徑所含公共點(diǎn)個(gè)數(shù)小于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).

取特殊點(diǎn)

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經(jīng)過2+(n-2)(n-4)長途徑所到達(dá)的公共點(diǎn)的個(gè)數(shù)小于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中經(jīng)過2+(n-3)(n-3)長途徑至少含有n-1個(gè)公共點(diǎn), 從而kn-1(D:x,y)≤2+(n-3)(n-3).

即在D中v1經(jīng)過1+(n-3)(n-3)長途徑所到達(dá)的點(diǎn)的個(gè)數(shù)小于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.

[責(zé)任編輯：王軍]

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

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

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

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

O157.5

A

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