強競賽圖中頂點的外弧泛圈性.pdf

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

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

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

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

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

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

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