多部競賽圖中包含在圈中的孤.pdf

1、多部競賽圖無疑是有向圖中一類重要的圖，并且它已經(jīng)被廣泛研究.競賽圖是頂點(diǎn)數(shù)為c的c-部競賽圖.關(guān)于競賽圖中有向路和有向圈問題的研究非常深入而且成果豐碩.將競賽圖的結(jié)果推廣到多部競賽圖中是研究多部競賽圖的有效途徑之一.一個(gè)向圖D的Hamiltonian圈指的是一個(gè)包含D的所有頂點(diǎn)的圈.稱有向圖D是泛圈的，如果它包含從3到|V(D)|的每個(gè)長度的圈.稱有向圖D的一個(gè)頂點(diǎn)（一條?。┦欠喝Φ模绻鼘儆诿總€(gè)l-圈(3≤l≤|V(D)|).稱有向

2、圖D是頂點(diǎn)泛圈（弧泛圈）的，如果它的每個(gè)頂點(diǎn)（?。┦欠喝Φ?目前，在競賽圖的泛圈性、頂點(diǎn)泛圈性及弧泛圈性方面已有了很多結(jié)果.有向圖D的一條從頂點(diǎn)x出發(fā)的弧被稱為是x的一條外弧.如果一個(gè)頂點(diǎn)的所有外弧在D中都是泛圈的，則稱這個(gè)頂點(diǎn)是外弧泛圈頂點(diǎn).2000年，Yao，Guo和Zhang首次對競賽圖中頂點(diǎn)的外弧泛圈性作了討論，證明了強(qiáng)競賽圖中外弧泛圈頂點(diǎn)的存在性.而對于強(qiáng)多部競賽圖，連Hamiltonian圈的存在都不能保證.因此，退一步講，

3、在c-部競賽圖中，我們考慮屬于l-圈(3≤l≤c)的頂點(diǎn)（?。?，以及屬于頂點(diǎn)恰巧來自l(3≤l≤c)個(gè)不同部集的圈的頂點(diǎn)（?。?1994年，Moon證明了強(qiáng)競賽圖至少存在三條泛弧.考慮到Moon的結(jié)果，Volkmann在2007年提出的一個(gè)猜想:每個(gè)強(qiáng)c(c≥3)-部競賽圖至少包含三條弧，其中每條弧屬于一個(gè)m-圈Cm，對每個(gè)m∈{3，4，...，c}.本文主要研究強(qiáng)多部競賽圖中上述弧的存在性，證明了Volkmann的猜想，從而推廣了上述