尤利華， 陳 芳

(華南師范大學數學科學學院，廣東廣州 510631)

本原有向圖Dn,q,s的scrambling指數

尤利華*， 陳 芳

(華南師范大學數學科學學院，廣東廣州 510631)

本原有向圖; scrambling 指數; 缺數段; 指數集

稱有向圖D是本原的,如果存在正整數k,使得對于D中的任意2點vi和vj(允許i=j),在D中都存在從點vi到點vj長為k的有向途徑.這樣的最小正整數k稱為D的本原指數,記為exp(D).眾所周知,有向圖D是本原的當且僅當D是強連通的且其所有圈長的最大公約數(簡記為g.c.d.)為1.記所有的n階本原有向圖的集合為Pn.

AKELBEK和KIRKLAND[1]給出了有向圖的scrambling指數和局部scrambling指數的定義. 事實上，scrambling指數和局部scrambling指數與PAZ[2]定義的公共后續(xù)指數及局部公共后續(xù)指數是一回事. 當有向圖是本原有向圖時，它們與文獻[3]定義的有向圖的競賽指數的定義是一樣的. 關于其研究進展，可參見文獻[1]-[16].

顯然Dn,q,s是本原有向圖. 事實上,Dn,q,s是組合矩陣論中一類重要的(極)圖.例如：文獻[18]在研究本原有向圖的本原指數時,Dn,n,n-1就是取到本原指數最大值(n-1)2+1的圖D1;文獻[19]在研究本原幾乎可約有向圖的本原指數時,Dn,n-1,s就是取到其本原指數最大值n+s(n-3)的圖Dn-1,s;文獻[17]在研究本原有向圖的Lewin數時，Dn,n-1,s就是取到Lewin數最大值的圖Dn-1,s;在本原有向圖的局部指數和其帶號有向圖的基指數的研究中所涉及到的極圖也是圖類Dn,q,s中某些具體的圖[18,20].同樣,在研究本原有向圖的scrambling指數和m-competition指數時其極圖也是Dn,q,s中某些具體的圖[1,5-6,8-9,11-13,15-16],等等.

本文研究了本原有向圖Dn,q,s的scrambling指數,提出了1個公開問題.

1 本原有向圖Dn,q,s的scrambling指數

引理1[1]設q,s是兩正整數，滿足g.c.d.(q,s)=1,2≤s

注1 在文獻[1]中，由引理1的證明易知方程xq+ys=t的具有最小絕對值的整數解就是滿足xq+ys=t且|x|≤?s/2」,|y|≤?q/2」的整數解.

引理2[1]設D是n階本原有向圖,q,s是D的兩不同的圈長,若g.c.d.(q,s)=1,2≤s

ku,v(D)≤min{|y|s,|x|q}+lu,v,

(1)

注2 由于|y|≤?q/2」,|x|≤?s/2」,所以

ku,v(D)≤min{|y|s,|x|q}+lu,v≤

min{?q/2」s,?s/2」q}+lu,v.

(2)

記Dn,q,s中長為s,q的圈分別為Cs,Cq. 以下,令U=V(Cs)∩V(Cq)={n-q+1,…,s}. 因為q+s≥n+1,故U≠.以下以d(u,v)表示有向圖中點u到點v的最短路的長度.

引理3 設n,q,s,Dn,q,s如上文所定義，則

k(Dn,q,s)≤min{?q/2」s,?s/2」q}+n-s=

(3)

證明當s=1時，k≤n-1,結論成立.

當s≥2時，以下分6種情形：

ki, j(Dn,q,s)≤min{?q/2」s,?s/2」q}+n-s.

(4)

對于情形1～情形3，均取n-q+1為雙圈點，則li, j=max{l(i,n-q+1),l(j,n-q+1)}≤n-s, 由引理2知式(4)成立.下面證明在情形4～情形6下式(4)成立.

子情形4.1:s是奇數.

子情形4.2.2:1≤t

子情形4.2.3:t>s/2.此時d(j,i)=s-t,且s-t

子情形5.1:s是奇數.

子情形5.1.1:若xq-ys=t.此時同子情形4.1.1的證明.

子情形5.2：s是偶數.此時由g.c.d.(q,s)=1知q必為奇數，從而y≤(q-1)/2.

子情形5.2.1：若ys-xq=t.此時同子情形4.2.2.2的證明.

子情形5.2.2：若xq-ys=t.此時1≤t=d(i,j)≤s-1，可分以下3種情形證明.

子情形5.2.2.1:若1≤t

子情形5.2.2.3:若t=s/2,則

(1)若s/2≤n-s.此時取j為雙圈點，則li, j=max{l(i,j),l(j,j)}≤n-s,再由引理2得

子情形6.1:s是偶數.此時q必為奇數.以下分2種情形證明.

子情形6.1.1:若d(j,i)≤n-s.取i為雙圈點,則li, j=max{l(i,i),l(j,i)}≤n-s，再由引理2知

子情形6.2:s是奇數.

子情形6.2.1:若d(j,i)≤n-s.此時同子情形6.1.1的證明.

子情形6.2.2:若d(j,i)≥n-s+1.此時類似于子情形6.1.2的證明.

□

□

以下以p(u,v)表示有向圖中點u到點v的有向路的長度.

□

(1)若p(s+1,n-q+1)>p(v,n-q+1),記p(s+1,n-q+1)-p(v,n-q+1)=t1s+d1,其中t1,d1為非負整數且0≤d1≤s-1.

(i)當d1≥1且存在非負整數x,y,x≤?s/2」,y≤?q/2」,使得xq-ys=d1,則

ks+1,v(Dn,q,s)=xq+p(v,n-q+1)=(y-t1)s+n-s.

(ii)當d1≥1且存在非負整數x,y,x≤?s/2」,y≤?q/2」,使得ys-xq=d1,則

ks+1,v(Dn,q,s)=xq+n-s=(y+t1)s+p(v,n-q+1).

(2)若p(s+1,n-q+1)

(iii)當d2≥1且存在非負整數x,y,x≤?s/2」,y≤?q/2」,使得ys-xq=d2,則

ks+1,v(Dn,q,s)=xq+p(v,n-q+1)=(y+t2)s+n-s.

(iv)當d2≥1且存在非負整數x,y,x≤?s/2」,y≤?q/2」,使得xq-ys=d2,則

ks+1,v(Dn,q,s)=xq+n-s=(y-t2)s+p(v,n-q+1).

證明首先由引理4可知點s+1與點v通過最短的相同途經長所到達的公共點為n-q+1,故ks+1,v(Dn,q,s)等于點s+1與點v到達公共點n-q+1的最短相同途經長.

注意到點s+1到點n-q+1只有唯一的一條路，故p(s+1,n-q+1)=n-s,設W1、W2是點s+1與點v到達公共點n-q+1的2條同長途徑，則W1(W2)是點s+1(點v)到點n-q+1的有向路與若干個圈之并,從而有非負整數x1,x2,y1,y2使

下面先證明(i)和(ii)成立.

情形1：若x2≥x1.下證y2

從而(x2-x1)q+(y2-y1)s=t1s+d1,其中x2-x1和y2-y1均為非負整數.

由引理5知p(s+1,n-q+1)-p(v,n-q+1)=t1s+d1

故有(x2-x1)q-(y1-y2+t1)s=d1.此時，若存在非負整數x,y,x≤?s/2」,y≤?q/2」,使得xq-ys=d1,則由注1知ks+1,v(Dn,q,s)=xq+p(v,n-q+1)=(y-t1)s+n-s,即(i)成立.

情形2：若x2x2q+y2s,又p(s+1,n-q+1)>p(v,n-q+1),則W1與W2不可能等長.故y1

故有(y2-y1-t1)s-(x1-x2)q=d1.此時，若存在非負整數x,y,x≤?s/2」,y≤?q/2」,使得ys-xq=d1,則由注1知ks+1,v(Dn,q,s)=xq+n-s=(y+t1)s+p(v,n-q+1),即(ii)成立.

結論(iii)、(iv)的證明與以上證明類似,故略去.

□

引理7 設n,q,s,Dn,q,s如上文定義，記

則

證明情形1：若s是偶數. 此時q必定為奇數,可分如下2種情形證明.

子情形1.2.1: 若p(v,n-q+1)=n-s/2.此時p(v,n-q+1)-p(s+1,n-q+1)=s/2. 再由sq/2-(q-1)s/2=s/2及引理6之(iv)可知此情形下點s+1與點v到點n-q+1的最短相同途徑長為(q-1)s/2+n-s/2.

子情形1.2.2: 若p(v,n-q+1)=n-3s/2+q.此時p(v,n-q+1)-p(s+1,n-q+1)=q-s/2≤n-s/2≤3s/2-s/2=s.再由(q,s)=1知q-s/2=s當且僅當s=2,n=q=3,可直接驗證結論成立.以下僅考慮q-s/2≤s-1 的情形. 由(q-1)s/2-(s/2-1)q=q-s/2及引理6之(iii)可知此情形下點s+1與點v到達點n-q+1的最短相同途徑長為(q-1)s/2+n-s.

情形2: 若s為奇數. 此時按q的奇偶性可分2種情形討論.

子情形2.1： 若s是奇數，q是偶數.設q/2=gs+r,其中g,r為非負整數且0≤r≤s-1. 再由g.c.d.(q,s)=1知1≤r≤s-1.

子情形2.1.2.1：若p(v,n-q+1)=n-s+r.此時p(v,n-q+1)-p(s+1,n-q+1)=r,再由(q/2-g)s-(s-1)q/2=r及引理6之(iii)可知此情形下點s+1與點v到點n-q+1的最短相同途徑長為(s-1)q/2+n-s+r.

子情形2.1.2.2： 若p(v,n-q+1)=n-q+r.

子情形2.1.2.2.1：若g=0. 此時1≤q/2=r≤s-1,1≤p(v,n-q+1)-p(s+1,n-q+1)=s-q+r=s-q/2

子情形2.1.2.2.2：若g≥1.此時p(s+1,n-q+1)-p(v,n-q+1)=r+(2g-1)s,且有(q/2-g)s-(s-1)q/2=r成立,則由引理6之(ii)可知此情形下點s+1與點v到點n-q+1的最短相同途徑長為(s-1)q/2+n-s.

情形2.2: 若s是奇數，q是奇數.設(q-s)/2=gs+r,其中g,r為非負整數,且0≤r≤s-1. 再由g.c.d.(q,s)=1知1≤r≤s-1.此時類似于子情形2.1的證明.

綜上可知結論成立.

□

定理1

k(Dn,q,s)=min{?q/2」s,?s/2」q}+n-s=

注意到文獻[1]定義的極圖Ds,n為本文的圖Dn,n,s,文獻[12]定義的圖Hn、圖Qn和圖Wn分別為本文的圖Dn,n-1,n-2、圖Dn,n-2,n-3和圖Dn,n-1,n-3(這里n為偶數),所以文獻[1]中定理3.10及文獻[12]中引理3.10～引理3.12等結論均可為定理1的推論.

2 展望

注意到若D是n階本原有向圖,其本原指數exp(D)與scrambling指數k(D)之間似乎存在某些內在的緊密聯系，例如由文獻[18]知其上界滿足exp(D)≤(n-1)2+1,由文獻[1]、[4]知k(D)≤「((n-1)2+1)/2?.下面再來看一些具體的圖類.

由文獻[10],若D是n階本原對稱矩陣的伴隨有向圖,其本原指數與scrambling指數滿足k(D)=「exp(D)/2?.

由文獻[20],若D=Dn,q,s是本原有向圖,其本原指數exp(D)=sq+n-2s，再由定理1知

由文獻[18],若D是恰含d個環(huán)的n階本原有向圖,其本原指數exp(D)≤2n-d+1，而由文獻[7]、[12],其scrambling指數k(D)≤n-「d/2?.

由文獻[18],若D是n階完全不可分陣的伴隨有向圖,其本原指數exp(D)≤n-1,而由文獻[12],其scrambling指數k(D)≤「(n-1)/2?.

由文獻[18],若D是n階本原幾乎可約陣的伴隨有向圖,其本原指數exp(D)≤n2-4n+6,由文獻[5]、[12],其scrambling指數k(D)≤「(n2-4n+7)/2?.

因此有

[1] AKELBEK M,KIRKLAND S. Coefficients of ergodicity and the scrambling index[J]. Linear Algebra Appl,2009,430: 1111-1130.

[2] PAZ A. Introduction to probabilistic automata[M]. New York,London:Academic Press,1971.

[3] CHO H H,KIM H K. Competition indices of digraphs[C]∥Proceedings of Workshop in Combinatorices,2004: 99-107.

[4] SCHWARZ S. Common consequents in directed graphs[J]. Czechoslovak Math J,1985,35(2): 212-247.

[5] ZHOU B. On the common consequent indices of nearly reducible binary relations[J]. Util Math,1999,56: 233-243.

[6] ZHOU B,LIU B L. New results on the common consequent index of a binary relation[J].European J Combin,2000,21(2): 167-179.

[7] MA H P,MIAO ZH K. On the set of common consequent indices of a class of binary relations[J]. Journal of Mathematical Research and Exposition,2008,28(3):460-468.

[8] AKELBEK M,KIRKLAND S. Primitive digraphs with the largest scrambling index[J]. Linear Algebra Appl,2009,430: 1099-1110.

[9] AKELBEK M,FITAL S,SHEN J. A bound on the scrambling index of a primitive matrix using Boolean rank[J].Linear Algebra Appl,2009,431: 1923-1931.

[10] CHEN S X,LIU B L. The scrambling index of symmetric primitive matrices[J]. Linear Algebra Appl,2010,433：1110-1126.

[11] KIM H K. Generalized competition index of a primitive digraph[J]. Linear Algebra Appl,2010,433: 72-79.

[12] LIU B L,HUANG Y F. The scrambling index of primitive digraphs[J]. Comput Math Appl,2010,60: 706-721.

[13] LIU B L,HUANG Y F. Generalized scrambling indices of a primitive digraph[J]. Linear Algebra Appl,2010,433: 1798-1808.

[14] SIM M S,KIM H K. On generalized competition index of a primitive tournament[J]. Discrete Math, 2011,311: 168-182.

[15] KIM H K,LEE S H. Generalized competition indices of symmetric primitive digraphs[J].Discrete Appl Math,2012,160: 1583-1590.

[16] KIM H K,PARK S G. A bound of generalized competition index of a primitive digraph[J]. Linear Algebra Appl,2012,436: 86-98.

[17] SHEN J. On a problem of Lewin[J]. Linear Algebra Appl,1998,274: 411-426.

[18] LIU B L,LAI H J. Matrices in combinatorics and graph theory[M]. Dordrecht:Kluwer Academic Publishers,2000.

[19] ROSS J A. On the exponent of a primitive nearly reducible matrix[J]. SIAM J Alg Discrete Math,1982,3: 395-410.

[20] 吳鈺涵，尤利華. 一類重要的本原(帶號)有向圖的指數值[J]. 華南師范大學學報:自然科學版，2011(3): 44-48.

Keywords： primitive digraph; scrambling index; gaps; index set

TheScramblingIndexofPrimitiveDigraphsDn,q,s

YOU Lihua*, CHEN Fang

(School of Mathematical Sciences,South China Normal University,Guangzhou 510631, China)

2012-07-03

國家自然科學基金項目(10901061,11071088)；廣州市珠江科技新星專項資助項目(2011J2200090)

*通訊作者:尤利華，教授，Email: ylhua@scnu.edu.cn.

1000-5463(2013)05-0007-06

O151.21

A

10.6054/j.jscnun.2013.07.002

【中文責編：莊曉瓊 英文責編：肖菁】