本原有向圖Dn,q,s的scrambling指數(shù)

尤利華， 陳 芳

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

本原有向圖Dn,q,s的scrambling指數(shù)

尤利華*， 陳 芳

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

本原有向圖; scrambling 指數(shù); 缺數(shù)段; 指數(shù)集

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

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

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

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

1 本原有向圖Dn,q,s的scrambling指數(shù)

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

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

引理2[1]設(shè)D是n階本原有向圖,q,s是D的兩不同的圈長(zhǎng),若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中長(zhǎng)為s,q的圈分別為Cs,Cq. 以下,令U=V(Cs)∩V(Cq)={n-q+1,…,s}. 因?yàn)閝+s≥n+1,故U≠.以下以d(u,v)表示有向圖中點(diǎn)u到點(diǎn)v的最短路的長(zhǎng)度.

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

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

(3)

證明當(dāng)s=1時(shí)，k≤n-1,結(jié)論成立.

當(dāng)s≥2時(shí)，以下分6種情形：

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

(4)

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

子情形4.1:s是奇數(shù).

子情形4.2.2:1≤t

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

子情形5.1:s是奇數(shù).

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

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

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

子情形5.2.2：若xq-ys=t.此時(shí)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.此時(shí)取j為雙圈點(diǎn)，則li, j=max{l(i,j),l(j,j)}≤n-s,再由引理2得

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

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

子情形6.2:s是奇數(shù).

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

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

□

□

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

□

(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為非負(fù)整數(shù)且0≤d1≤s-1.

(i)當(dāng)d1≥1且存在非負(fù)整數(shù)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)當(dāng)d1≥1且存在非負(fù)整數(shù)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)當(dāng)d2≥1且存在非負(fù)整數(shù)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)當(dāng)d2≥1且存在非負(fù)整數(shù)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可知點(diǎn)s+1與點(diǎn)v通過最短的相同途經(jīng)長(zhǎng)所到達(dá)的公共點(diǎn)為n-q+1,故ks+1,v(Dn,q,s)等于點(diǎn)s+1與點(diǎn)v到達(dá)公共點(diǎn)n-q+1的最短相同途經(jīng)長(zhǎng).

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

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

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

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

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

故有(x2-x1)q-(y1-y2+t1)s=d1.此時(shí)，若存在非負(fù)整數(shù)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不可能等長(zhǎng).故y1

故有(y2-y1-t1)s-(x1-x2)q=d1.此時(shí)，若存在非負(fù)整數(shù)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)成立.

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

□

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

則

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

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

子情形1.2.2: 若p(v,n-q+1)=n-3s/2+q.此時(shí)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當(dāng)且僅當(dāng)s=2,n=q=3,可直接驗(yàn)證結(jié)論成立.以下僅考慮q-s/2≤s-1 的情形. 由(q-1)s/2-(s/2-1)q=q-s/2及引理6之(iii)可知此情形下點(diǎn)s+1與點(diǎn)v到達(dá)點(diǎn)n-q+1的最短相同途徑長(zhǎng)為(q-1)s/2+n-s.

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

子情形2.1： 若s是奇數(shù)，q是偶數(shù).設(shè)q/2=gs+r,其中g(shù),r為非負(fù)整數(shù)且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.此時(shí)p(v,n-q+1)-p(s+1,n-q+1)=r,再由(q/2-g)s-(s-1)q/2=r及引理6之(iii)可知此情形下點(diǎn)s+1與點(diǎn)v到點(diǎn)n-q+1的最短相同途徑長(zhǎng)為(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. 此時(shí)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.此時(shí)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)可知此情形下點(diǎn)s+1與點(diǎn)v到點(diǎn)n-q+1的最短相同途徑長(zhǎng)為(s-1)q/2+n-s.

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

綜上可知結(jié)論成立.

□

定理1

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

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

2 展望

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

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

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

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

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

由文獻(xiàn)[18],若D是n階本原幾乎可約陣的伴隨有向圖,其本原指數(shù)exp(D)≤n2-4n+6,由文獻(xiàn)[5]、[12],其scrambling指數(shù)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] 吳鈺涵，尤利華. 一類重要的本原(帶號(hào))有向圖的指數(shù)值[J]. 華南師范大學(xué)學(xué)報(bào):自然科學(xué)版，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

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

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

1000-5463(2013)05-0007-06

O151.21

A

10.6054/j.jscnun.2013.07.002

【中文責(zé)編：莊曉瓊 英文責(zé)編：肖菁】