強(qiáng)競(jìng)賽圖中頂點(diǎn)的外弧泛圈性.pdf

1、競(jìng)賽圖無(wú)疑是有向圖中一類(lèi)非常重要的圖，并且它已經(jīng)被廣泛研究.關(guān)于競(jìng)賽圖中有向路和有向圈問(wèn)題的研究非常深入而且成果豐碩.稱(chēng)有向圖D是泛圈的，如果它包含從3到|V(D)|的每個(gè)長(zhǎng)度的圈.稱(chēng)有向圖D的一個(gè)頂點(diǎn)（一條?。┦莐泛的，如果它屬于每個(gè)l-圈（k≤l≤|V（D）|）.當(dāng)k=3時(shí)，也稱(chēng)該頂點(diǎn)（弧）是泛圈的.稱(chēng)有向圖D是頂點(diǎn)泛圈（弧泛圈）的，如果它的每個(gè)頂點(diǎn)（?。┦欠喝Φ?對(duì)某個(gè)k∈{3，4，…，|V(D)|},稱(chēng)有向圖D是弧-k-圈的，如

2、果D的每條弧都包含在一個(gè)長(zhǎng)為k的圈中.顯然，有向圖D是弧泛圈的當(dāng)且僅當(dāng)對(duì)每個(gè)k=3，4，…，|V(D)|，它是弧-k-圈的.目前，在競(jìng)賽圖的泛圈性、頂點(diǎn)泛圈性及弧泛圈性方面已有了很多結(jié)果.有向圖D的一條從頂點(diǎn)x出發(fā)的弧被稱(chēng)為是x的一條外弧.如果一個(gè)頂點(diǎn)的所有外弧在D中都是k泛的，則稱(chēng)這個(gè)頂點(diǎn)是外弧k泛頂點(diǎn).當(dāng)k=3時(shí)，也稱(chēng)該頂點(diǎn)是外弧泛圈頂點(diǎn).2000年，Yao，Guo和Zhang首次對(duì)競(jìng)賽圖中頂點(diǎn)的外弧泛圈性作了討論，證明了強(qiáng)競(jìng)賽圖中

3、外弧泛圈頂點(diǎn)的存在性.本文主要研究強(qiáng)競(jìng)賽圖中頂點(diǎn)的外弧泛圈性問(wèn)題.
　　本文共分五章.第一章介紹了有向圖中的一些相關(guān)的基本概念以及論文內(nèi)容的安排.
　　第二章回顧了競(jìng)賽圖中的一些相關(guān)結(jié)果.
　　第三章研究了強(qiáng)競(jìng)賽圖中外弧泛圈頂點(diǎn)的個(gè)數(shù).在2000年，Yao，Guo和Zhang證明了每個(gè)強(qiáng)競(jìng)賽圖T都包含一個(gè)外弧泛圈頂點(diǎn).同時(shí)他們提出一個(gè)猜想:每個(gè)k-強(qiáng)競(jìng)賽圖至少存在k個(gè)這樣的頂點(diǎn).現(xiàn)在已經(jīng)證明了該猜想對(duì)k=1，2，3是對(duì)

4、的.然而，由于Yeo給出的下面的例子，這個(gè)猜想對(duì)k≥4是不成立的.設(shè)T1，T2和T3都是階至少為k的可遷競(jìng)賽圖.T是在Ti之間添加弧得到的一個(gè)競(jìng)賽圖，使得T1(→)T2(→)T3(→)T1.顯然T是k-強(qiáng)的.由于Ti中的任何一條弧都不在T的一個(gè)3-圈中，所以僅有在每個(gè)Ti(i=1，2，3)中出度為零的頂點(diǎn)是T的外弧泛圈頂點(diǎn).但是Yeo提出的下列猜想可能是正確的:每個(gè)2-強(qiáng)競(jìng)賽圖至少包含3個(gè)外弧泛圈頂點(diǎn).在3.2節(jié)，我們證明了Yeo的猜想

5、是成立的.另外，對(duì)于最小出度為1的強(qiáng)競(jìng)賽圖，Yao等人找到一個(gè)強(qiáng)競(jìng)賽圖的無(wú)限類(lèi)使得其中每個(gè)強(qiáng)競(jìng)賽圖恰包含一個(gè)外弧泛圈頂點(diǎn).那么我們自然要問(wèn):對(duì)于最小出度至少為2的強(qiáng)競(jìng)賽圖包含幾個(gè)外弧泛圈頂點(diǎn)呢？在3.3節(jié)，我們證明了連通度為1且最小出度至少是2的強(qiáng)競(jìng)賽圖也至少包含3個(gè)外弧泛圈頂點(diǎn)，并舉例說(shuō)明了這個(gè)結(jié)果的最佳可能性.結(jié)合3.2和3.3節(jié)的這兩個(gè)結(jié)論，我們得到具有最小出度至少是2的強(qiáng)競(jìng)賽圖至少包含3個(gè)外弧泛圈頂點(diǎn).
　　第四章研究了恰

6、有3個(gè)外弧泛圈頂點(diǎn)的強(qiáng)競(jìng)賽圖.Yeo在2005年給出一類(lèi)例子說(shuō)明對(duì)任意的正整數(shù)k，存在一類(lèi)k-強(qiáng)競(jìng)賽圖，使得其中每個(gè)競(jìng)賽圖至多包含3個(gè)外弧泛圈頂點(diǎn).那么除了這類(lèi)例子以外，是否k-強(qiáng)競(jìng)賽圖就包含k外弧泛圈頂點(diǎn)？本章中，我們給出了恰有3個(gè)外弧泛圈頂點(diǎn)的5-強(qiáng)競(jìng)賽圖的一個(gè)必要條件，證明了恰有3個(gè)外弧泛圈頂點(diǎn)的5-強(qiáng)競(jìng)賽圖是某一類(lèi)圖中的成員.設(shè)T1，T2和T3都是階為k≥5的強(qiáng)競(jìng)賽圖，滿足u，v1和w1分別是T1，T2和T3中出度為零的頂點(diǎn)，且

7、有（V（T1）-{u}）→u，（V（T2）-{v1}）→v1及（V（T3）-{w1}）→w1.設(shè)T4是一個(gè)競(jìng)賽圖.令T0是在Ti(i=1，2，3，4)之間添加弧得到的所有強(qiáng)競(jìng)賽圖的集合，使得T1(→)T2(→)T3(→)T1且T4中的每個(gè)頂點(diǎn)都控制{u，v1，w1}，其它的弧任意定向.設(shè)T是一個(gè)恰包含3個(gè)外弧泛圈頂點(diǎn)的5-強(qiáng)競(jìng)賽圖，則T是T0中的一個(gè)成員.我們的結(jié)果表明，除T0以外，5-強(qiáng)競(jìng)賽圖一定包含4個(gè)外弧泛圈頂點(diǎn).
　　第五