一個含四個圈的本原有向圖的m-competition指數(shù)

宋卓蓉，高玉斌

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

?

一個含四個圈的本原有向圖的m-competition指數(shù)

宋卓蓉，高玉斌

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

[摘要]對于n階本原有向圖D中任意頂點(diǎn)u和v,若都存在m(1≤m≤n)個不同的頂點(diǎn)v1,v2,…,vm∈V(D), 使得成立，則稱最小正整數(shù)k為本原有向圖D的m-competition指數(shù). 本文研究了一類含有一個n長圈、三個n-2長圈的本原有向圖, 確定了本原有向圖的m-competition指數(shù).

[關(guān)鍵詞]本原有向圖; m-competition指數(shù); 圈

1預(yù)備知識

本原有向圖本原指數(shù)的研究已經(jīng)逐步擴(kuò)展到了對本原有向圖的scrambling指數(shù)的研究.本原有向圖的scrambling 指數(shù)是一個新興研究分支，也是近兩年來在組合數(shù)學(xué)中較為活躍的一個研究方向，在計算機(jī)科學(xué)中具有廣泛的實(shí)際應(yīng)用背景.2009年,文獻(xiàn)[2]中作者提出了本原圖的scrambling指數(shù)的概念. 2010年,文獻(xiàn)[4]將本原圖的scrambling指數(shù)推廣到m-competition指數(shù)，并對指數(shù)達(dá)到的上界進(jìn)行了極圖刻畫．

設(shè)D=(V,E)是一個n階有向圖, 其中頂點(diǎn)集V=V(D), 弧集E=E(D)(允許有環(huán)但無重弧).一個有向圖D是本原的，當(dāng)且僅當(dāng)存在正整數(shù)k，使得D中的任意一點(diǎn)u到另外一點(diǎn)v(v可能等于u)都存在k長途徑.稱滿足上述條件的最小正整數(shù)k為有向圖D的本原指數(shù)，記為exp(D).

設(shè)D一個n階本原有向圖,k∈Z+, 對于任意x,y∈V(D),用N+(Dk:x，y)=N+(Dk:x)∩N+(Dk:y)表示頂點(diǎn)x的k步外鄰域.用N+(Dk:x，y)表示頂點(diǎn)x,y的k步公共外鄰域.

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

2主要結(jié)論及證明

設(shè)n≥7,n為奇數(shù),本文主要研究了一個含一個n圈和3個n-2圈的n階本原有向圖，計算得到了此類本原有向圖的m-competition指數(shù).

定理1設(shè)D是一個n階本原有向圖,如圖1所示,其中n≥7,n為奇數(shù),則對任意1≤m≤n:

證明由本原有向圖D，可以得到有向圖Dn-2和Dn.

圖1　有向圖D

1)m=1

V(Dn)={v1,v2,…,vn}

圖2　有向圖Dn

觀察圖D，頂點(diǎn)v1,v2,…,vn-4,vn-1,vn構(gòu)成一個n-2圈，不妨將這個n-2圈記為C. 在圖Dn中，令M=Dn[{v1,v2,…,vn-4,vn-1,vn}]，M為Dn的一個導(dǎo)出子圖.其中

V(M)={v1,v2,…,vn-4,vn-1,vn},

E(M)=E(Dn)-{(vn-4,vn-2),(vn-2,vn),(vn-5,vn-3),(vn-3,vn-1)}

在圖M中,對任意vi、vj∈V(M),因?yàn)?/p>

故

所以

2)m為奇數(shù)，3≤m≤n

在Dn-2中,

圖3　有向圖Dn-2

V(Dn-2)={v1,v2,…,vn}

∪{(vn-3,vn-1),(vn-2,vn)}

故對任意u,v∈V(D),均有

所以

={vn-4,…,vn-m+2,vn-m}.

故

∪{vn-m,…,vn-1}.

所以

3)m為偶數(shù)，2≤m≤n-1

故對任意u、v∈V(D),均有

所以

={vn-5,vn-7,…,vn-m-2}.

故

{vn-m-1,…,vn-5}

所以

定理得證.

[參考文獻(xiàn)]

[1]BrualdiRA,RyserHJ.Combinatorialmatrixtheory[M].Cambridgc：CambridgeUniversityPress,1991.

[2]AkelbekM,KirklandS.Coefficientsofergodicityandthescramblingindex[J].LinearAlgebraanditsApplications, 2009, 430:1099-1110.

[3]HuangYF,LiuBL.Generalizedscramblingindicesofaprimitivedigraphs[J].LinearAlgebraanditsApplications, 2010, 433:1798-1808.

[4]KimHK.Generalizedcompetitionindexofaprimitivedigraph[J].LinearAlgebraanditsApplications, 2010, 433: 72-79.

[5]GaoYB,ShaoYL.Thescramblingindicesofprimitivedigraphswithexactlytwocycles[J].ArsCombination, 2013, 108:505-513.

[6]ShaoYL,GaoYB.Them-competitionindicesofsymmetricprimitivedigraphswithloop[J].ArsCombination, 2013, 108: 217-223.

[7]KimHK,PankSG.Aboundofgeneralizedcompetitionindexofaprimitivedigraph[J].LinearAlgebraanditsApplications, 2012, 436: 86-98.

[8]KimHK,LeeSH.Generalizedcompetitionindicesofsymmetricprimitivedigraphs[J].DiscreteAppliedMathematics， 2012, 160: 1583-1590.

(責(zé)任編輯穆剛)

The m-competition index of a primitive digraph with four cycles

SONG Zhuorong, GAO Yubin

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

Abstract：For positive integers m and n with 1≤m≤n, the m-competition index of a primitive digraph D of order n is the smallest positive integer k such that for every pair of vertices u and v, if there is m distinct vertices v1,v2,…,vm∈V(D) such that there are walks of length k from u to viand from v to vifor 1≤i≤m. In this paper, the m-competition indices of a primitive digraph with one n-cycle and three (n-2)-cycles were studied and the m-competition index of this primitive digraph was determined.

Key words：primitive digraph; m-competition index; cycle

[中圖分類號]O157.5

[文獻(xiàn)標(biāo)志碼]A

[文章編號]1673-8004(2015)05-0018-04

[通訊作者]高玉斌(1962—)，男，山西忻州人，教授，博士生導(dǎo)師.

[作者簡介]宋卓蓉(1990— )，女，山西長治人，在讀研究生，主要從事組合數(shù)學(xué)方面的研究.

[基金項(xiàng)目]國家自然科學(xué)基金項(xiàng)目(11071227).

[收稿日期]2015-03-12